A polynomial-space exact algorithm for TSP in degree-6 graphs

DOI10.1007/978-3-319-48532-4_20MaRDI QIDQ2958106zbMATH OpenOpenAlexFDO

Authors Norhazwani M.D. Yunos, Aleksandar Shurbevski, Hiroshi Nagamochi

Publication date 1 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-48532-4_20

zbMATH Keywords

branch-and-reduceexact exponential algorithmmeasure-and-conquertraveling salesman problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Recommendations

• An improved exact algorithm for TSP in graphs of maximum degree 4
• An improved exact algorithm for TSP in degree-4 graphs
• A \(\frac{9}{7}\)-approximation algorithm for graphic TSP in cubic bipartite graphs

Cites work

• A measure \& conquer approach for the analysis of exact algorithms
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• An Improved Exact Algorithm for Cubic Graph TSP
• An improved exact algorithm for TSP in graphs of maximum degree 4
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Exact Algorithms for Maximum Independent Set
• Exact exponential algorithms.
• Expected Computation Time for Hamiltonian Path problem
• The Traveling Salesman Problem for Cubic Graphs

Cited in

(3)

• An improved exact algorithm for TSP in degree-4 graphs
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

This page was built for publication: A polynomial-space exact algorithm for TSP in degree-6 graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958106)