An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs

DOI10.1016/0166-218X(83)90042-2zbMath0511.05042OpenAlexW2131762752MaRDI QIDQ1838978

Takahiro Watanabe, Takao Nishizeki, Takao Asano

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(83)90042-2

zbMATH Keywords

closed spanning walkgeneralized hamiltonian cycle problemhamiltonian walk

Mathematics Subject Classification ID

Graph theory (05C99) Eulerian and Hamiltonian graphs (05C45) Algorithms in computer science (68W99)

Related Items (11)

Connected max cut is polynomial for graphs without the excluded minor \(K_5\backslash e\) ⋮ On the Hamiltonian number of a plane graph ⋮ The Hamiltonian Number of Cubic Graphs ⋮ Hamiltonian numbers in oriented graphs ⋮ A Simple 2-Approximation for Maximum-Leaf Spanning Tree ⋮ Hamiltonian numbers of Möbius double loop networks ⋮ The Hamiltonian numbers in digraphs ⋮ Spanning closed walks and TSP in 3-connected planar graphs ⋮ Hamiltonian spectra of graphs ⋮ Graph theory (algorithmic, algebraic, and metric problems) ⋮ The upper traceable number of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel concepts in graph theory
• A Theorem on Planar Graphs
• An upper bound on the length of a Hamiltonian walk of a maximal planar graph
• Efficient Planarity Testing
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamiltonian circuits on 3-polytopes
• On Hamiltonian Walks in Graphs

This page was built for publication: An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs