The Travelling Salesman Problem in Bounded Degree Graphs

DOI10.1007/978-3-540-70575-8_17zbMath1152.90575OpenAlexW1824848400MaRDI QIDQ3521919

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto

Publication date: 28 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (19)

Spotting Trees with Few Leaves ⋮ Set multi-covering via inclusion-exclusion ⋮ Spotting Trees with Few Leaves ⋮ Treewidth computation and extremal combinatorics ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ Simplifying Inclusion–Exclusion Formulas ⋮ Breaking the \(2^{n}\)-barrier for irredundance: two lines of attack ⋮ Fast polynomial-space algorithms using inclusion-exclusion. Improving on Steiner tree and related problems ⋮ Finding and enumerating Hamilton cycles in 4-regular graphs ⋮ An exact algorithm for the Boolean connectivity problem for \(k\)-CNF ⋮ Complexity and approximability of the cover polynomial ⋮ Solving SCS for bounded length strings in fewer than \(2^n\) steps ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Complexity of the Bollobás-Riordan polynomial. Exceptional points and uniform reductions ⋮ Unnamed Item ⋮ The Exponential Time Complexity of Computing the Probability That a Graph Is Connected ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ An exact algorithm for TSP in degree-3 graphs via circuit procedure and amortization on connectivity structure

Uses Software

• Concorde

This page was built for publication: The Travelling Salesman Problem in Bounded Degree Graphs