Options
Computing 2-walks in polynomial time
Publikationstyp
Journal Article
Date Issued
2018
Sprache
English
Author(s)
TORE-URI
Journal
Volume
14
Start Page
22.1
End Page
22.18
Citation
ACM transactions on algorithms (2018)
Publisher DOI
Publisher
TALG
A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions.
We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, into which the graph is decomposed, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above. Its running time is O(n³).
We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, into which the graph is decomposed, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above. Its running time is O(n³).
DDC Class
510: Mathematik