Dynamic programming and planarity: Improved tree-decomposition based algorithms |
| |
Authors: | Frederic Dorn |
| |
Institution: | Department of Informatics, University of Bergen, N-5020 Bergen, Norway |
| |
Abstract: | We study some structural properties for tree-decompositions of 2-connected planar graphs that we use to improve upon the runtime of tree-decomposition based dynamic programming approaches for several NP-hard planar graph problems. E.g., we derive the fastest algorithm for Planar Dominating Set of runtime 3tw⋅nO(1), when we take the width tw of a given tree-decomposition as the measure for the exponential worst case behavior. We also introduce a tree-decomposition based approach to solve non-local problems efficiently, such as Planar Hamiltonian Cycle in runtime 6tw⋅nO(1). From any input tree-decomposition of a 2-connected planar graph, one computes in time O(nm) a tree-decomposition with geometric properties, which decomposes the plane into disks, and where the graph separators form Jordan curves in the plane. |
| |
Keywords: | Tree-decompositions Dynamic programming Planar dominating set Planar Hamiltonian cycle Planar graph TSP Branch-decompositions |
本文献已被 ScienceDirect 等数据库收录! |
|