Euclidean TSP in narrow strips

DOI10.1007/S00454-023-00609-7MaRDI QIDQ6541986zbMATH OpenFDO

Authors Mark de Berg, Remco van der Hofstad, Sándor Kisfaludi-Bak

Publication date 21 May 2024

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

Full work available at URL https://doi.org/10.1007/S00454-023-00609-7

zbMATH Keywords

bitonic TSPcomputational geometryEuclidean TSPfixed-parameter tractable algorithms

Mathematics Subject Classification ID

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

Recommendations

• Euclidean TSP in narrow strips
• Euclidean TSP with few inner points in linear space
• Computing and Combinatorics
• The traveling salesman problem with few inner points
• Euclidean TSP on two polygons

Cites work

• An introduction to the theory of point processes
• Computational geometry. Algorithms and applications.
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient special case algorithms for the n-line planar traveling salesman problem
• Fine-grained complexity analysis of two classic TSP variants
• Fine-grained Complexity Analysis of Two Classic TSP Variants
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 1416816 (Why is no real title available?)
• Introduction to algorithms.
• Moment recurrence relations for binomial, Poisson and hypergeometric frequency distributions.
• On the approximability of the maximum common subgraph problem
• On the complexity of k-SAT
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Subexponential algorithms for rectilinear Steiner tree and arborescence problems
• Testing the necklace condition for shortest tours and optimal factors in the plane
• The Convex-hull-and-k-line Travelling Salesman Problem
• The convex-hull-and-line traveling salesman problem: A solvable case
• The Euclidean traveling salesman problem is NP-complete
• The n-line traveling salesman problem
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• The traveling salesman problem with few inner points

Cited in

(1)

• An ETH-Tight Exact Algorithm for Euclidean TSP

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

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