The Travelling Salesman Problem in Bounded Degree Graphs
From MaRDI portal
Publication:3521919
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
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
This page was built for publication: The Travelling Salesman Problem in Bounded Degree Graphs
