Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Decompositions |
| |
Authors: | Frederic Dorn Eelko Penninkx Hans L. Bodlaender Fedor V. Fomin |
| |
Affiliation: | 1. Department of Informatics, University of Bergen, 5020, Bergen, Norway 2. Department of Information and Computing Sciences, Utrecht University, P.O. Box 80.089, 3508 TB, Utrecht, The Netherlands
|
| |
Abstract: | We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an $O(2^{6.903sqrt{n}})We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an O(26.903?n)O(2^{6.903sqrt{n}}) time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time O(29.8594?n)O(2^{9.8594sqrt{n}}) . Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given k decides if a planar graph on n vertices has a cycle of length at least k in time O(213.6?kn+n3)O(2^{13.6sqrt{k}}n+n^{3}) . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|