An Improved Exact Algorithm for Cubic Graph TSP
From MaRDI portal
Publication:3608837
DOI10.1007/978-3-540-73545-8_13zbMATH Open1206.68146DBLPconf/cocoon/IwamaN07OpenAlexW1542928981WikidataQ56138399 ScholiaQ56138399MaRDI QIDQ3608837FDOQ3608837
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
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
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cited In (23)
- 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
- Title not available (Why is that?)
- Finding and enumerating Hamilton cycles in 4-regular graphs
- Approximation hardness of graphic TSP on cubic graphs
- Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
- Exact algorithms for finding longest cycles in claw-free graphs
- 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
- A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
- Parameterized Edge Dominating Set in Cubic Graphs
- Hamiltonicity and the 3-Opt procedure for the traveling Salesman problem
- Spotting Trees with Few Leaves
- Spotting Trees with Few Leaves
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The Travelling Salesman Problem in Bounded Degree Graphs
- Finding 2-factors closer to TSP tours in cubic 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}
- Cubic TSP: A 1.3-Approximation
- Parameterized edge dominating set in graphs with degree bounded by 3
- 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)
