TSP in a simple polygon

DOI10.4230/LIPICS.ESA.2022.5MaRDI QIDQ6969686zbMATH OpenFDO

Authors Mark de Berg, Morteza Monemizadeh, Leonidas Theocharous

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.5

zbMATH Keywords

subexponential algorithmstraveling salesman problemTSP with obstacles

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A gap-ETH-tight approximation scheme for Euclidean TSP
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• A quasi-polynomial algorithm for well-spaced hyperbolic TSP
• A subexponential parameterized algorithm for subset TSP on planar graphs
• An ETH-tight exact algorithm for Euclidean TSP
• Approximating TSP on metrics with bounded global growth
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Euclidean TSP on two polygons
• Finding small simple cycle separators for 2-connected planar graphs
• Geometric separator theorems and applications
• 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 1303538 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• Non-Euclidean Traveling Salesman Problem
• On subexponential parameterized algorithms for Steiner tree and directed subset TSP on planar graphs
• Optimal shortest path queries in a simple polygon
• Parameterized algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• The Euclidean traveling salesman problem is NP-complete
• The searching over separators strategy to solve some NP-hard problems in subexponential time
• The traveling salesman problem and its variations
• The traveling salesman problem. A computational study.
• The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme
• The traveling salesman. Computational solutions for RSP applications
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

Cited in

(3)

• A coreset for approximate furthest-neighbor queries in a simple polygon
• Clustering in polygonal domains
• Realizing metric spaces with convex obstacles

This page was built for publication: TSP in a simple polygon

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