Parameterized Algorithms on Width Parameters of Graphs
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,...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2012
|
| Témata: | |
| On-line přístup: | http://is.muni.cz/th/99352/fi_d/ |
| Shrnutí: | 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ů. The subject of the thesis is the study of the parameterized complexity approach in developing graph algorithms. The approach allows the use of so-called parameters to obtain efficient graph algorithms on a very wide class of graphs. The thesis focuses on providing and proving algorithms for a range of graph problems, giving hardness results and proving various structural and algorithmic properties of graphs. Most of the thesis focuses on a relatively new structural parameter called rank-width. It shows that rank-width is a very powerful tool for dealing with a large number of interesting problems on graphs, including the design of efficient parameterized algorithms for many interesting problems on the large class of graphs of bounded rank-width. The thesis also provides an overview of various previously considered parameters on directed graphs and compares these to a directed version of rank-width with respect to how useful these parameters are in the design of parameterized algorith |
|---|---|
| Popis jednotky: | Vedoucí práce: Petr Hliněný |
| Fyzický popis: | 143 s. |