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

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)

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 exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• 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 (4)

• Improved algorithms for graph four-connectivity
• A Polynomial-Space Exact Algorithm for TSP in Degree-6 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)