The Shortest Separating Cycle Problem

DOI10.1007/978-3-319-51741-4_1zbMath1484.68326OpenAlexW2570519564MaRDI QIDQ2971152

No author found.

Publication date: 4 April 2017

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-51741-4_1

zbMATH Keywords

traveling salesman problemshortest separating cycle

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items

On the shortest separating cycle

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of approximating TSP with neighborhoods and related problems
• The Euclidean traveling salesman problem is NP-complete
• Approximation algorithms for the Geometric Covering Salesman Problem
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• Approximation algorithms for TSP with neighborhoods in the plane
• Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics
• How Long Can a Euclidean Traveling Salesman Tour Be?
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane