TSP on Cubic and Subcubic Graphs

DOI10.1007/978-3-642-20807-2_6zbMath1339.90274OpenAlexW1582969422MaRDI QIDQ3009751

Suzanne Van der Ster, Sylvia Boyd, Leen Stougie, R. A. Sitters

Publication date: 24 June 2011

Published in: Integer Programming and Combinatoral Optimization (Search for Journal in Brave)

Full work available at URL: https://research.vu.nl/en/publications/2a00f5db-1978-45e7-a632-3c2b4eab44f3

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (11)

Approximation hardness of graphic TSP on cubic graphs ⋮ Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies ⋮ A 4/3-approximation for TSP on cubic 3-edge-connected graphs ⋮ The parity Hamiltonian cycle problem ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ The traveling salesman problem on cubic and subcubic graphs ⋮ Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs ⋮ Improved integrality gap upper bounds for traveling salesperson problems with distances one and two ⋮ TSP Tours in Cubic Graphs: Beyond 4/3 ⋮ The Parity Hamiltonian Cycle Problem in Directed Graphs ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Matchings in regular graphs
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• Maximum Cardinality Simple 2-matchings in Subcubic Graphs
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems
• Unions of perfect matchings in cubic graphs
• 8/7-approximation algorithm for (1,2)-TSP
• The traveling salesman problem on a graph and some related integer polyhedra
• Heuristic analysis, linear programming and branch and bound
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Fractional Packing ofT-Joins
• The Traveling Salesman Problem with Distances One and Two
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Maximum matching and a polyhedron with 0,1-vertices
• Blocking and anti-blocking pairs of polyhedra

This page was built for publication: TSP on Cubic and Subcubic Graphs