A new upper bound for the traveling salesman problem in cubic graphs

DOI10.1016/j.jda.2014.02.001zbMath1361.68109arXiv1207.4694OpenAlexW2048163742MaRDI QIDQ2250536

Maciej Liśkiewicz, Martin Schuster

Publication date: 7 July 2014

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1207.4694

zbMATH Keywords

Hamiltonian cycletraveling salesman problemcubic graphsexact algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

Special Frequency Quadrilaterals and an Application ⋮ Unnamed Item ⋮ The distribution of edge-frequencies computed with frequency quadrilaterals for traveling salesman problem ⋮ An improved exact algorithm for TSP in graphs of maximum degree 4 ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

Cites Work

• Unnamed Item
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Dynamic cage survey
• The traveling salesman problem in bounded degree graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• A Dynamic Programming Approach to Sequencing Problems
• An Improved Exact Algorithm for Cubic Graph TSP
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The Traveling Salesman Problem for Cubic Graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: A new upper bound for the traveling salesman problem in cubic graphs