Parameterized Algorithms on Width Parameters of Graphs - Ganian, Robert (2012)
Předmětem práce je aplikování parametrizovaného přístupu k vývoji algoritmů pro různé grafové problémy. Přístup využívá tzv. parametrů k vývoji efektivních algoritmů na velmi obecných třídách grafů. Většina práce se zaměřuje na rankovou šířku jakožto relativně nový strukturální parametr. Ukazujeme, že ranková šířka je velmi užitečným nástrojem k vývoji efektivních algoritmů na obecnější třídě grafů než jsou grafy s omezenou stromovou šířkou. Práce také předkládá sumarizaci a srovnání mnoha uvažovaných parametrů na orientovaných grafech. Výsledky tohoto srovnání vychází v prospěch orientované verze rankové šířky. Obsahem práce je také několik obecných výsledků o dříve uvažovaných orientovaných parametrech. Poslední část práce obsahuje řadu doplňujících vsledků, jako je např. analýza parametrizované složitosti problémů Max-Rep a Min-Rep a výhodný způsob zobecnění vrcholového pokrytí jakožto parametru k řešení velmi těžkých problémů.