The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

DOI10.4230/lipics.ipec.2020.23arXiv2007.12120OpenAlexW3115157686MaRDI QIDQ6089670

Konrad Majewski, Łukasz Kowalik

Publication date: 13 November 2023

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

zbMATH Keywords

Hamiltonian cycleasymmetric traveling salesman problemsparse graphsexponential algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• 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
• Finding and enumerating Hamilton cycles in 4-regular graphs
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• On two techniques of combining branching and treewidth
• Dynamic programming meets the principle of inclusion and exclusion
• A short proof of Minc's conjecture
• The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
• Finding all the perfect matchings in bipartite graphs
• Faster exponential-time algorithms in graphs of bounded average degree
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs
• The traveling salesman problem in bounded degree graphs
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Expected Computation Time for Hamiltonian Path problem
• A Search Procedure for Hamilton Paths and Circuits
• Fast Hamiltonicity Checking Via Bases of Perfect Matchings
• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Directed Hamiltonicity and Out-Branchings via Generalized Laplacians
• Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
• A Bound on the Pathwidth of Sparse Graphs with Applications to Exact Algorithms
• On the Number of Hamilton Cycles in Bounded Degree Graphs
• The Traveling Salesman Problem for Cubic Graphs
• Spotting Trees with Few Leaves
• Determinant Sums for Undirected Hamiltonicity
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time

This page was built for publication: The Asymmetric Travelling Salesman Problem In Sparse Digraphs.