An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure (Q262259): Difference between revisions

From MaRDI portal
Merged Item from Q4922118
Normalize DOI.
 
(2 intermediate revisions by one other user not shown)
Property / DOI
 
Property / DOI: 10.1007/s00453-015-9970-4 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1007/S00453-015-9970-4 / rank
 
Normal rank
Property / cites work
 
Property / cites work: The traveling salesman problem in bounded degree graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions / rank
 
Normal rank
Property / cites work
 
Property / cites work: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Traveling Salesman Problem for Cubic Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Automata, Languages and Programming / rank
 
Normal rank
Property / cites work
 
Property / cites work: Exact exponential algorithms. / rank
 
Normal rank
Property / cites work
 
Property / cites work: Finding and enumerating Hamilton cycles in 4-regular graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Improved Exact Algorithm for Cubic Graph TSP / rank
 
Normal rank
Property / cites work
 
Property / cites work: A linear time algorithm for computing 3-edge-connected components in a multigraph / rank
 
Normal rank
Property / cites work
 
Property / cites work: Algorithmic Aspects of Graph Connectivity / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4414647 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Improved Exact Algorithm for TSP in Degree-4 Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure / rank
 
Normal rank
Property / cites work
 
Property / cites work: The Travelling Salesman Problem in Bounded Degree Graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth / rank
 
Normal rank
Property / cites work
 
Property / cites work: A new upper bound for the traveling salesman problem in cubic graphs / rank
 
Normal rank

Latest revision as of 01:07, 28 December 2024

scientific article; zbMATH DE number 6167742
  • An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure
Language Label Description Also known as
English
An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure
scientific article; zbMATH DE number 6167742
  • An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure

Statements

An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure (English)
0 references
An Exact Algorithm for TSP in Degree-3 Graphs via Circuit Procedure and Amortization on Connectivity Structure (English)
0 references
0 references
0 references
29 March 2016
0 references
28 May 2013
0 references
The authors present a deterministic algorithm for TSP in degree-3 graphs, which runs in \(O^*(2^{\frac3{10}n})= O^*(1.2312^n)\) time and polynomial space. This improves the previous time bounds of \(O^*(1.251^n)\) by Iwama and Nakashima and \(O(1.260^n)\) by Eppstein. The algorithm is simple and contains only one branch rule (include/exclude edge) that is designed on a cut-circuit structure of a graph induced by unprocessed edges. The crucial point of the paper is the application of the measure and conquer method to analyze the running time. An amortization scheme over the cut-circuit structure of graphs is invented, wherein the authors introduce not only weights of vertices but also weights of \(U\)-components to define the measure of an instance. The idea of amortization schemes introducing weights on components may yield better bounds for other exact algorithms for graph problems when it is successfully analyzed how reduction/ branching procedures change the system of components.
0 references
traveling salesman problem
0 references
exact exponential algorithm
0 references
graph algorithm
0 references
connectivity
0 references
measure and conquer method
0 references
exact exponential algorithms
0 references
cubic graphs
0 references
measure and conquer
0 references

Identifiers

0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references
0 references