Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

DOI10.4230/LIPICS.ESA.2019.23MaRDI QIDQ5075760zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, Łukasz Kowalik

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1908.09325

zbMATH Keywords

\(k\)-OPTbounded degreetraveling salesman problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Fine-grained complexity analysis of two classic TSP variants
• Fine-grained Complexity Analysis of Two Classic TSP Variants
• Improving TSP tours using dynamic programming over tree decompositions
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• The Travelling Salesman Problem in Bounded Degree Graphs

Cites work

• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Can you beat treewidth?
• Finding and counting given length cycles
• Fine-grained complexity analysis of two classic TSP variants
• General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 1082106 (Why is no real title available?)
• scientific article; zbMATH DE number 2064412 (Why is no real title available?)
• Improving TSP tours using dynamic programming over tree decompositions
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• The parameterized complexity of local search for TSP, more refined
• The traveling-salesman problem and minimum spanning trees: Part II

Cited in

(11)

• Fine-grained Complexity Analysis of Two Classic TSP Variants
• On the \({\mathcal {H}}\)-free extension complexity of the TSP
• scientific article; zbMATH DE number 7651222 (Why is no real title available?)
• Graph clustering problems under the Lens of parameterized local search
• Parameterized local search for vertex cover: when only the search radius is crucial
• On polynomial kernels for traveling salesperson problem and its generalizations
• Can local optimality be used for efficient data reduction?
• Graph clustering problems under the Lens of parameterized local search
• Can you link up with treewidth?
• Can you link up with treewidth?
• Parameterized complexity of directed traveling salesman problem

Describes a project that uses

Uses Software

• LKH

This page was built for publication: Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP

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