Original title:
Obtížné problémy vzhledem k parametru různorodost sousedství
Translated title:
Obtížné problémy vzhledem k parametru různorodost sousedství
Authors:
Koutecký, Martin ; Kolman, Petr (advisor) ; Fiala, Jiří (referee) Document type: Master’s theses
Year:
2013
Language:
eng Abstract:
[eng][cze] Parameterized complexity is a part of computer science dealing with the computational complexity of problems measured not only by the length of their input but also some parameter of the input. Nei- ghborhood diversity is a recently introduced parameter describing a certain structure of a graph. is parameter is aractive for resear especially because some problems whi are hard with respect to other parameters that are incomparable with neighborhood diversity become fixed-parameter tractable with respect to neighborhood diversity. In this thesis we show fixed-parameter tractability for three problems that are hard with respect to treewidth. is constitutes the main part of this thesis and it is our original work. Next it contains an overview of other interesting problems and also a survey of the state of the art in the area of parameters for sparse and dense graphs. 1Parametrizovaná složitost je oblast teoretié informatiky zabývající se výpočetní složitostí pro- blémů měřenou nikoliv pouze délkou vstupu, ale i nějakým jeho parametrem. "Různorodost soused- ství" je nový strukturální parametr grafu, který je atraktivní především proto, že pro grafy s pevnou různorodostí sousedství se stávají efektivně řešitelnými i některé problémy, jež zůstávají těžké pro jiné parametry s různorodostí sousedství neporovnatelnými. V této práci nově ukazujeme efektivní řeši- telnost vzhledem k různorodosti sousedství pro tři problémy těžké vzhledem ke stromové šířce. To tvoří hlavní část této práce a jedná se o náš vlastní výzkum. Dále pak práce obsahuje přehled další zajímavý problémů a také shrnutí současného stavu v oblasti parametrů pro řídké a husté grafy. 1
Keywords:
dense graphs; neighborhood diversity; Parameterized complexity; husté grafy; Parametrizovaná složitost; různorodost sousedství
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/61447