An Improved Exact Algorithm for TSP in Degree-4 Graphs

DOI10.1007/978-3-642-32241-9_7zbMath1364.68236OpenAlexW2263686347MaRDI QIDQ2914313

Hiroshi Nagamochi, Mingyu Xiao

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

graph algorithmtraveling salesman problemexact exponential algorithm

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 (2)

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

This page was built for publication: An Improved Exact Algorithm for TSP in Degree-4 Graphs