A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs

DOI10.1007/978-3-319-48532-4_20zbMath1482.68275OpenAlexW2323549733MaRDI QIDQ2958106

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

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

traveling salesman problemexact exponential algorithmmeasure-and-conquerbranch-and-reduce

Mathematics Subject Classification ID

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

• 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
• Exact exponential algorithms.
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Exact Algorithms for Maximum Independent Set
• A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
• A measure & conquer approach for the analysis of exact algorithms
• An Improved Exact Algorithm for Cubic Graph TSP
• Expected Computation Time for Hamiltonian Path problem
• The Traveling Salesman Problem for Cubic Graphs

This page was built for publication: A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs