An improved exact algorithm for TSP in degree-4 graphs

DOI10.1007/978-3-642-32241-9_7MaRDI QIDQ2914313zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

Publication date 25 September 2012

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

Full work available at URL https://doi.org/10.1007/978-3-642-32241-9_7

zbMATH Keywords

exact exponential algorithmgraph algorithmtraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• An improved exact algorithm for TSP in graphs of maximum degree 4
• An Improved Exact Algorithm for Cubic Graph TSP
• A polynomial-space exact algorithm for TSP in degree-6 graphs

Cited in

(7)

• An improved exact algorithm for TSP in graphs of maximum degree 4
• Improved algorithms for graph four-connectivity
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP
• Improving TSP tours using dynamic programming over tree decompositions
• An Improved Exact Algorithm for Cubic Graph TSP
• The Travelling Salesman Problem in Bounded Degree Graphs

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

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