|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
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ě,...
|
|
|
Computational Complexity in Graph Theory
Jelínková, Eva ; Kratochvíl, Jan (vedoucí práce) ; Manlove, David (oponent) ; Fiala, Jiří (oponent)
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ě,...
|
host ::
RSS.