An Improved Exact Algorithm for Cubic Graph TSP

DOI10.1007/978-3-540-73545-8_13zbMath1206.68146DBLPconf/cocoon/IwamaN07OpenAlexW1542928981WikidataQ56138399 ScholiaQ56138399MaRDI QIDQ3608837

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

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

Related Items (16)

Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ Parameterized edge dominating set in graphs with degree bounded by 3 ⋮ A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Finding and enumerating Hamilton cycles in 4-regular graphs ⋮ Parameterized Edge Dominating Set in Cubic Graphs ⋮ A new upper bound for the traveling salesman problem in cubic graphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Unnamed Item ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ 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

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