The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
From MaRDI portal
Publication:6089670
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
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.