Bergen Open Research Archive >
Faculty of Mathematics and Natural Sciences >
Department of Informatics >
Department of Informatics >
Denne identifikatoren kan du bruke til å sitere eller lenke til denne innførselen:
http://hdl.handle.net/1956/2449
|
| Tittel: | Designing Subexponential Algorithms : Problems, Techniques & Structures |
| Forfattere: | Dorn, Frederic |
| Dato: | 14-Sep-2007 |
| Forlag: | The University of Bergen |
| Sammendrag: | In this thesis we focus on subexponential algorithms for NP-hard graph problems: exact
and parameterized algorithms that have a truly subexponential running time behavior.
For input instances of size n we study exact algorithms with running time 2O(√n) and
parameterized algorithms with running time 2O(√k) ·nO(1) with parameter k, respectively.
We study a class of problems for which we design such algorithms for three different types
of graph classes: planar graphs, graphs of bounded genus, and H-minor-free graphs. We
distinguish between unconnected and connected problems, and discuss how to conceive
parameterized and exact algorithms for such problems.
We improve upon existing dynamic programming techniques used in algorithms solving
those problems. We compare tree-decomposition and branch-decomposition based
dynamic programming algorithms and show how to unify both algorithms to one single
algorithm. Then we give a dynamic programming technique that reduces much
of the computation involved to fast matrix multiplication. In this manner, we obtain
branch-decomposition based algorithms on numerous problems, such as Vertex Cover
and Dominating Set. We also show how to exploit planarity for obtaining faster dynamic
programming approaches, a) in connection with fast matrix multiplication and b)
for tree-decompositions.
Furthermore, we focus on connected problems in particular, and their relation to the
input graph structure. We state the basis for how the latter problems can be attacked
for graph classes that inherit the Catalan structure. Truly subexponential algorithms for
edge-subset problems such as k-Longest Path and Planar Graph TSP are derived
by employing the planar graph structure. Moreover, we investigate how to obtain truly
subexponential algorithms for torus-embedded graphs, bounded genus graph and Hminor-
free graphs, by first using planarization techniques, and then proving the Catalan
structure for the planarized instances. |
| URI: | http://hdl.handle.net/1956/2449 |
| ISBN: | 978-82-308-0421-6 (print version) |
| Vises i samlingene: | Department of Informatics
|
Alle innførsler i BORA er beskyttet av opphavsrett
