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

DOI10.1007/S00224-015-9612-XMaRDI QIDQ255262zbMATH OpenOpenAlexFDO

Authors Mingyu Xiao, Hiroshi Nagamochi

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

exact exponential algorithmgraph algorithmmeasure-and-conquertraveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05)

Recommendations

• An improved exact algorithm for TSP in degree-4 graphs
• An improved approximation algorithm for the maximum TSP
• A refined algorithm for maximum independent set in degree-4 graphs
• Improved deterministic approximation algorithms for max TSP
• An Improved Exact Algorithm for Cubic Graph TSP
• An improved randomized approximation algorithm for Max TSP
• Improved algorithms for graph four-connectivity
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• Algorithms – ESA 2005
• Better approximations for max TSP

Cites work

• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A measure \& conquer approach for the analysis of exact algorithms
• A new upper bound for the traveling salesman problem in cubic graphs
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• An Improved Exact Algorithm for Cubic Graph TSP
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• An improved exact algorithm for TSP in degree-4 graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Exact exponential algorithms.
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• The Traveling Salesman Problem for Cubic Graphs
• The traveling salesman problem in bounded degree graphs

Cited in

(6)

• Improved algorithms for graph four-connectivity
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• An improved exact algorithm for TSP in degree-4 graphs
• The traveling salesman problem in bounded degree graphs
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• The Travelling Salesman Problem in Bounded Degree Graphs

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

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