arXiv preprint ·
Faster Planar Graph Algorithms for Connectivity Problems via Meanders
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
In this paper, we refine the dynamic programming framework based on the sphere cut decomposition designed by Dorn, Penninkx, Bodlaender, and Fomin (ESA 2005) to obtain faster subexponential algorithms for connectivity problems on planar graphs. We investigate the relationship between these problems and meanders, which are simple closed planar loops that intersect a fixed line in a given number of points. By combining dynamic programming with techniques from meandric system analysis and the use of fast matrix multiplication by Dorn (ESA 2006), we obtain improved algorithms for planar connectivity problems. We show that the number of meanders on $2n$ crossings $M_n$ is $\mathcal O^*(12.806^n)$, which improves the previous upper bound of $\mathcal O^*(12.901^n)$ by Albert and Paterson (FPSAC 2004). This then gives the best-known classical upper bounds on the deterministic time complexity of several planar graph problems with polynomially-bounded weights, namely $\mathcal O(2^{5.543\sqrt n})$ for the Planar Travelling Salesman problem, $\mathcal O(2^{5.796\sqrt n})$ for Planar Longest Cycle/Path, $\mathcal O(2^{8.251\sqrt n})$ for Planar Connected Dominating Set and $\mathcal O(2^{8.037\sqrt n})$ for Planar Steiner Tree. Notably, this leads to the best-known deterministic complexity $\mathcal O(2^{5.543\sqrt{n}})$ for the Planar Hamiltonian Cycle problem.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Improved classical optimization of fermionic Hamiltonians beyond Gaussian states
Tight bounds and output sensitive algorithms for maximal clique enumeration in link streams
Conditional Indexing Lower Bounds and Normalization Boundaries for Elastic Subsequence Matching
The chromatic number of the associahedron: simple and logarithmic
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.