Publikace na Matematicko-fyzikální fakulta |
2009
Abstrakt
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.