Exact algorithms for the Hamiltonian cycle problem in planar graphs

DOI10.1016/j.orl.2005.04.013zbMath1089.05040OpenAlexW2037995626WikidataQ57311716 ScholiaQ57311716MaRDI QIDQ2494820

Bettina Klinz, Gerhard J. Woeginger, Vladimir G. Deǐneko

Publication date: 30 June 2006

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2005.04.013

zbMATH Keywords

combinatorial optimizationplanar separator theorem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45)

Related Items

On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs, Good triangulations yield good tours, The homogeneous broadcast problem in narrow and wide strips. I: Algorithms, Sublinear separators, fragility and subexponential expansion, An ETH-Tight Exact Algorithm for Euclidean TSP, Catalan structures and dynamic programming in \(H\)-minor-free graphs, Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions, Subexponential parameterized algorithms, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Finding small simple cycle separators for 2-connected planar graphs
• Dynamic programming meets the principle of inclusion and exclusion
• Some simplified NP-complete graph problems
• The Euclidean traveling salesman problem is NP-complete
• Which problems have strongly exponential complexity?
• On the existence of subexponential parameterized algorithms
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• Dynamic Programming is Optimal for Nonserial Optimization Problems
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Hamilton Paths in Grid Graphs
• Mathematical Foundations of Computer Science 2004
• Graph Drawing
• On the complexity of \(k\)-SAT