Euclidean TSP in narrow strips

DOI10.1007/s00454-023-00609-7MaRDI QIDQ6541986

Unnamed Author, Remco van der Hofstad, Sándor Kisfaludi-Bak, Mark T. de Berg

Publication date: 21 May 2024

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

computational geometryEuclidean TSPfixed-parameter tractable algorithmsbitonic TSP

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An introduction to the theory of point processes
• The Euclidean traveling salesman problem is NP-complete
• Testing the necklace condition for shortest tours and optimal factors in the plane
• The convex-hull-and-line traveling salesman problem: A solvable case
• The Convex-hull-and-k-line Travelling Salesman Problem
• 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
• The traveling salesman problem with few inner points
• Moment recurrence relations for binomial, Poisson and hypergeometric frequency distributions.
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Efficient special case algorithms for the n-line planar traveling salesman problem
• The n-line traveling salesman problem
• 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
• Fine-grained complexity analysis of two classic TSP variants
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• Fine-grained Complexity Analysis of Two Classic TSP Variants
• On the approximability of the maximum common subgraph problem
• On the complexity of \(k\)-SAT

This page was built for publication: Euclidean TSP in narrow strips