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

DOI10.1007/s00224-015-9612-xzbMath1336.68276MaRDI 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 algorithm; traveling salesman problem; exact exponential algorithm; measure-and-conquer

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)