Parameterized Algorithms on Width Parameters of Graphs
| Authors | |
|---|---|
| Year of publication | 2012 |
| MU Faculty or unit | |
| Citation | |
| Description | 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. |
| Related projects: |