Spanning closed walks and TSP in 3-connected planar graphs

DOI10.1016/j.jctb.2014.04.002zbMath1301.05088OpenAlexW2101299686MaRDI QIDQ462924

Kenta Ozeki, Ken-ichi Kawarabayashi

Publication date: 22 October 2014

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jctb.2014.04.002

zbMATH Keywords

TSPintegrality gapclosed walk3-connected planar graphs4/3-conjectureHeld-Karp relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40)

Related Items (2)

Hamiltonicity of graphs on surfaces in terms of toughness and scattering number -- a survey ⋮ Types of triangle in Hamiltonian triangulations and an application to domination and k-walks

Cites Work

• 3-trees with few vertices of degree 3 in circuit graphs
• Graph minors. VII: Disjoint paths on a surface
• 4-connected projective planar graphs are Hamiltonian
• 2-walks in circuit graphs
• Subgraphs of graphs on surfaces with high representativity
• An approximation algorithm for the Hamiltonian walk problem on maximal planar graphs
• Worst-case comparison of valid inequalities for the TSP
• On the approximability of the traveling salesman problem
• Simple paths on polyhedra
• A Theorem on Planar Graphs
• An upper bound on the length of a Hamiltonian walk of a maximal planar graph
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Approximating Graphic TSP by Matchings
• Trees in Polyhedral Graphs
• The Traveling-Salesman Problem and Minimum Spanning Trees
• On Hamiltonian Circuits
• A theorem on paths in planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Spanning closed walks and TSP in 3-connected planar graphs