|
|
Metody pro obarvení uzlů multigrafu
Knotek, Martin ; Kunovský, Jiří (oponent) ; Šátek, Václav (vedoucí práce)
Tato práce se zabývá algoritmy pro vrcholové barvení a jejich aplikaci na barvení prvků elektrické rozvodné sítě nízkého napětí. Výsledkem práce je program zobrazující průběh barvení pěti implementovaných metod na zvoleném grafu, který představuje distribuční síť elektrické energie ve městě.
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
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.
|
|
|
Výpočetní složitost v teorii grafů
Doucha, Martin ; Kratochvíl, Jan (vedoucí práce) ; Dvořák, Zdeněk (oponent)
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.
|
|
|
Metody pro obarvení uzlů multigrafu
Knotek, Martin ; Kunovský, Jiří (oponent) ; Šátek, Václav (vedoucí práce)
Tato práce se zabývá algoritmy pro vrcholové barvení a jejich aplikaci na barvení prvků elektrické rozvodné sítě nízkého napětí. Výsledkem práce je program zobrazující průběh barvení pěti implementovaných metod na zvoleném grafu, který představuje distribuční síť elektrické energie ve městě.
|
host ::
RSS.