An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
From MaRDI portal
Publication:262259
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
graph algorithmconnectivitytraveling salesman problemcubic graphsexact exponential algorithmmeasure and conquer methodexact exponential algorithmsmeasure and conquer
Programming involving graphs or networks (90C35) Analysis of algorithms (68W40) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
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