2012
Parameterized Algorithms on Width Parameters of Graphs
GANIAN, RobertZákladní údaje
Originální název
Parameterized Algorithms on Width Parameters of Graphs
Autoři
GANIAN, Robert
Vydání
143 s. 2012
Další údaje
Typ výsledku
Účelové publikace
Utajení
není předmětem státního či obchodního tajemství
Organizační jednotka
Fakulta informatiky
Změněno: 12. 12. 2012 11:58, RNDr. Robert Ganian, Ph.D.
Anotace
V originále
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 algorithms. Interestingly, the results of this comparison are heavily in favor of the introduced directed version of rank-width. Furthermore, the thesis contains a range of supplementary results. These include an analysis of the parameterized complexity of the well-studied Max-Rep and Min-Rep problems with respect to various parameters, and the introduction of twin-cover, a generalization of vertex cover which may be used as a powerful graph parameter capable of solving many notoriously hard problems.
Návaznosti
| MSM0021622419, záměr |
| ||
| MUNI/A/0914/2009, interní kód MU |
|