An ETH-Tight Exact Algorithm for Euclidean TSP
From MaRDI portal
Publication:6156029
DOI10.1137/22m1469122arXiv1807.06933OpenAlexW2951388475MaRDI QIDQ6156029
Sudeshna Kolay, Mark T. de Berg, Sándor Kisfaludi-Bak, Hans L. Bodlaender
Publication date: 9 June 2023
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1807.06933
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- The Euclidean traveling salesman problem is NP-complete
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The searching over separators strategy to solve some NP-hard problems in subexponential time
- Open problems around exact algorithms
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Net and Prune
- Dynamic Programming Treatment of the Travelling Salesman Problem
- A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
- Minimum-weight triangulation is NP-hard
- Reducibility Among Combinatorial Problems
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Fast Hamiltonicity Checking Via Bases of Perfect Matchings
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- The limited blessing of low dimensionality
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
This page was built for publication: An ETH-Tight Exact Algorithm for Euclidean TSP
