velikost textu

Computational Complexity in Graph Theory

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Computational Complexity in Graph Theory
Název v češtině:
Výpočetní složitost v teorii grafů
Typ:
Disertační práce
Autor:
RNDr. Eva Jelínková
Školitel:
prof. RNDr. Jan Kratochvíl, CSc.
Oponenti:
Dr. David Manlove
doc. RNDr. Jiří Fiala, Ph.D.
Id práce:
43993
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
2. 6. 2016
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
Seidelovo přepnutí, teorie grafů, výpočetní složitost, problém trhu s domy, ekonomické ekvilibrium
Klíčová slova v angličtině:
Seidel's switching, graph theory, computational complexity, Housing Market problem, economic equilibrium
Abstrakt:
Abstrakt Název práce: Výpočetní složitost v teorii grafů Autor: Eva Jelínková Katedra: Katedra Aplikované Matematiky Vedoucí disertační práce: Prof. RNDr. Jan Kratochvíl, CSc., Katedra Aplikované Matematiky Abstrakt: Zabýváme se problémy teorie grafů, zejména z hlediska výpočetní složitosti. V první části práce se věnujeme výpočetní složitosti problémů sou- visejících se Seidelovým přepnutím grafů. Uvažujeme rozhodující problém, zda daný graf lze přepnout tak, aby obsahoval nejvýše daný počet hran. Dokážeme, že tento problém je NP-úplný, dokonce i pro grafy s omezenou hustotou. Částečně tak odpovídáme na otázku Matouška a Wagnera [Dis- crete Comput. Geom. 52, no. 1, 2014]. Popisujeme také nekonečně mnoho grafů H, pro které je NP-těžké rozhodnout, zda pro daný graf existuje graf, který je s ním ekvivalentní v přepnutí, a zároveň neobsahuje H jako induko- vaný podgraf. Tímto řešíme otevřený problém Kratochvíla, Nešetřila a Zýky [Annals of Discrete Math. 51, 1992]. Ve druhé části práce se zabýváme tématem párování s preferencemi. Zaměřujeme se na problém trhu s domy, konkrétně na model s duplicitními domy. Popisujeme 2-aproximační algoritmus pro maximální počet spoko- jených agentů v případě, kdy preferenční seznamy agentů jsou trichotomické. Zároveň ale dokazujeme, že tento počet je NP-těžké aproximovat s poměrem menším než 21/19, a pokud preferenční seznamy agentů nemusí být tri- chotomické, potom je těžké tento počet aproximovat s poměrem menším než 1.2. Kromě těchto výsledků také popisujeme asymptoticky optimální vylepšení algoritmu pro ekonomické ekvilibrium pro situaci, kdy preferenční seznamy agentů jsou ostrá lineární uspořádání typů domů. Klíčová slova: Seidelovo přepnutí, teorie grafů, výpočetní složitost, problém trhu s domy, ekonomické ekvilibrium
Abstract v angličtině:
Abstract Title: Computational Complexity in Graph Theory Author: Eva Jelínková Department: Department of Applied Mathematics Supervisor: Prof. RNDr. Jan Kratochvíl, CSc., Department of Applied Mathematics Abstract: We address problems from graph theory, especially from the computational complexity point of view. In the first part of the thesis we address the computational complexity of problems related to Seidel’s switch- ing of graphs. We prove that the problem to decide if a given graph can be switched to contain at most a given number of edges is NP-complete, even for graphs with bounded density. We thus partially answer a question of Matoušek and Wagner [Discrete Comput. Geom. 52, no. 1, 2014]. We also describe infinitely many graphs H such that it is NP-complete to decide if a given graph is switching-equivalent to a graph that does not contain H as an induced subgraph. We thus close an open problem of Kratochvíl, Nešetřil and Zýka [Annals of Discrete Math. 51, 1992]. In the second part of the thesis we address the topic of matchings under preferences. We focus on the housing market problem, in particular, on the model with duplicate houses. We present a 2-approximation algorithm for the maximum number of satisfied agents when the preference lists of agents are trichotomic. On the other hand, we prove that the number is NP-hard to approximate within a factor smaller than 21/19, and if the preferences are not required to be trichotomic, then the number is NP-hard to approxi- mate within a factor smaller than 1.2. In addition to these results, we show an asymptotically optimal improvement of the equilibrium algorithm in the setting where agents’ preferences are strict linear orderings of house types. Keywords: Seidel’s switching, graph theory, computational complexity, Housing Market problem, economic equilibrium
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Eva Jelínková 814 kB
Stáhnout Abstrakt v českém jazyce RNDr. Eva Jelínková 47 kB
Stáhnout Abstrakt anglicky RNDr. Eva Jelínková 46 kB
Stáhnout Posudek vedoucího prof. RNDr. Jan Kratochvíl, CSc. 279 kB
Stáhnout Posudek oponenta Dr. David Manlove 62 kB
Stáhnout Posudek oponenta doc. RNDr. Jiří Fiala, Ph.D. 193 kB
Stáhnout Záznam o průběhu obhajoby 111 kB