An improved exact algorithm for TSP in graphs of maximum degree 4
DOI10.1007/S00224-015-9612-XzbMATH Open1336.68276OpenAlexW1993804709MaRDI QIDQ255262FDOQ255262
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
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
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Nonnumerical algorithms (68W05)
Cites Work
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- A new upper bound for the traveling salesman problem in cubic graphs
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- An improved exact algorithm for TSP in degree-4 graphs
- Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
- The traveling salesman problem in bounded degree graphs
- A measure \& conquer approach for the analysis of exact algorithms
- An Improved Exact Algorithm for Cubic Graph TSP
- Title not available (Why is that?)
- The Traveling Salesman Problem for Cubic Graphs
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
- Exact exponential algorithms.
- Finding and enumerating Hamilton cycles in 4-regular 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)
