Original title:
Rozklady grafů
Translated title:
Rozklady grafů
Authors:
Škoda, Petr ; Kráľ, Daniel (advisor) ; Fiala, Jiří (referee) Document type: Master’s theses
Year:
2009
Language:
eng Abstract:
[eng][cze] The notion of submodular partition functions generalizes many of well-known tree decompositions of graphs. For fixed k, there are polynomialtime algorithms to determine whether a graph has tree-width, branch-width, etc. at most k. Contrary to these results, we show that there is no subexponential algorithm for determining whether the width of a given submodular partition function is at most two. In addition, we also develop another dual notion for submodular partition functions which is analogous to loose tangles for connectivity functions.Submodulární rozkladové funkce zobecňují známé druhy stromových rozkladů grafů. Pro každé pevné k existují polynomiální algoritmy, které rozhodují, zda je stromová či větvená šířka nejvýše k. My ukážeme, že neexistuje algoritmus, který by rozhodoval, zda je šířka dané submodulární rozkladové funkce nejvýše dva v čase menším než exponenciálním. Dále popíšeme novou duální strukturu pro submodulární rozkladové funkce podobnou volným zámotkům pro souvislostní funkce.
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/22348