An Improved Exact Algorithm for Cubic Graph TSP

DOI10.1007/978-3-540-73545-8_13MaRDI QIDQ3608837zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Takuya Nakashima, Kazuo Iwama

Publication date 6 March 2009

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

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_13

zbMATH Keywords

traveling salesman problem for graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Improved approximations for cubic bipartite and cubic TSP
• Improved Approximations for Cubic Bipartite and Cubic TSP
• An improved upper bound for the TSP in cubic 3-edge-connected graphs
• Cubic TSP: A 1.3-Approximation
• TSP on cubic and subcubic graphs
• A 4/3-approximation for TSP on cubic 3-edge-connected graphs
• Approximation hardness of graphic TSP on cubic graphs
• An improved exact algorithm for TSP in degree-4 graphs
• Graphic TSP in cubic graphs
• A new upper bound for the traveling salesman problem in cubic graphs

Cited in

(28)

• An improved exact algorithm for TSP in graphs of maximum degree 4
• The Traveling Salesman Problem for Cubic Graphs
• Finding and enumerating Hamilton cycles in 4-regular graphs
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• Parameterized edge dominating set in cubic graphs (extended abstract)
• Spotting trees with few leaves
• Spotting trees with few leaves
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Approximation hardness of graphic TSP on cubic graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• An improved exact algorithm for TSP in degree-4 graphs
• Moderate exponential-time algorithms for scheduling problems
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• A new upper bound for the traveling salesman problem in cubic graphs
• Exploiting sparsity for bipartite Hamiltonicity
• Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
• The traveling salesman problem in bounded degree graphs
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The traveling salesman problem for cubic graphs.
• The Travelling Salesman Problem in Bounded Degree Graphs
• Finding 2-factors closer to TSP tours in cubic graphs
• Supereulerian testing on semi-Eulerian graphs
• Improved Approximations for Cubic Bipartite and Cubic TSP
• A cubic algorithm for the directed Eulerian subgraph problem
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Parameterized edge dominating set in graphs with degree bounded by 3
• Cubic TSP: A 1.3-Approximation
• Moderate exponential-time algorithms for scheduling problems

This page was built for publication: An Improved Exact Algorithm for Cubic Graph TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3608837)