An improved exact algorithm for TSP in graphs of maximum degree 4

DOI10.1007/s00224-015-9612-xzbMath1336.68276OpenAlexW1993804709MaRDI QIDQ255262

Hiroshi Nagamochi, Mingyu Xiao

Publication date: 9 March 2016

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-015-9612-x

zbMATH Keywords

graph algorithmtraveling salesman problemexact exponential algorithmmeasure-and-conquer

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

Cites Work

• Unnamed Item
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• Exact exponential algorithms.
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• A new upper bound for the traveling salesman problem in cubic graphs
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• An Improved Exact Algorithm for TSP in Degree-4 Graphs
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• The traveling salesman problem in bounded degree graphs
• A measure & conquer approach for the analysis of exact algorithms
• An Improved Exact Algorithm for Cubic Graph TSP
• The Traveling Salesman Problem for Cubic Graphs
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs

This page was built for publication: An improved exact algorithm for TSP in graphs of maximum degree 4