Original title:
Výpočetní složitost v teorii grafů
Translated title:
Computational complexity in graph theory
Authors:
Doucha, Martin ; Kratochvíl, Jan (advisor) ; Dvořák, Zdeněk (referee) Document type: Master’s theses
Year:
2012
Language:
cze Abstract:
[cze][eng] Tato práce zavádí dvě nové parametrizace grafových úloh zobecňující vrcholové pokrytí, které v hierarchii grafových parametrizací vyplňují část prostoru mezi vrcholovým pokrytím a klikovou šířkou. Dále zde zkoumáme parametrizovanou složitost hledání Hamiltonovské cesty a kružnice, klasického barvení grafu, problému Precoloring extension a Equitable coloring pro tyto nové parametrizace. Kromě problému Precoloring extension, který je pro jednu parametrizaci W[1]-těžký, se pro všechny ostatní problémy podařilo najít FPT algoritmus pro obě parametrizace. Hranici mezi třídami FPT a W[1] se tak u těchto problémů podařilo posunout blíže směrem k parametrizaci klikovou šířkou.This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.
Keywords:
equitable coloring; Hamiltonian path; parameterized complexity; precoloring extension; vertex coloring; barvení grafu; equitable coloring; Hamiltonovská cesta; parametrizovaná složitost; precoloring extension
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/41278