An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

DOI10.1007/s00453-015-9970-4zbMath1348.90559arXiv1212.6831OpenAlexW3100213179WikidataQ56032471 ScholiaQ56032471MaRDI QIDQ262259

Mingyu Xiao, Hiroshi Nagamochi

Publication date: 29 March 2016

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1212.6831

zbMATH Keywords

graph algorithmconnectivitytraveling salesman problemcubic graphsexact exponential algorithmmeasure and conquer methodexact exponential algorithmsmeasure and conquer

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (10)

Spotting Trees with Few Leaves ⋮ Further improvements for SAT in terms of formula length ⋮ A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Unnamed Item ⋮ A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles ⋮ Unnamed Item ⋮ A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals ⋮ 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

Cites Work

• Unnamed Item
• An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
• Exact exponential algorithms.
• Finding and enumerating Hamilton cycles in 4-regular graphs
• A linear time algorithm for computing 3-edge-connected components in a multigraph
• 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 TSP in Degree-4 Graphs
• Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms
• The traveling salesman problem in bounded degree graphs
• The Travelling Salesman Problem in Bounded Degree Graphs
• Algorithmic Aspects of Graph Connectivity
• An Improved Exact Algorithm for Cubic Graph TSP
• The Traveling Salesman Problem for Cubic Graphs
• Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
• Automata, Languages and Programming

This page was built for publication: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure