The shortest separating cycle problem

DOI10.1007/978-3-319-51741-4_1MaRDI QIDQ2971152zbMATH OpenOpenAlexFDO

Authors

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

shortest separating cycletraveling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• On the shortest separating cycle
• The complexity of separating points in the plane
• The complexity of separating points in the plane
• SEPARATING POINTS BY AXIS-PARALLEL LINES
• Geometric multicut: shortest fences for separating groups of objects in the plane

Cites work

• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• A PTAS for TSP with neighborhoods among fat regions in the plane
• Approximation algorithms for the Geometric Covering Salesman Problem
• Approximation algorithms for TSP with neighborhoods in the plane
• Approximation schemes for degree-restricted MST and red-blue separation problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• How Long Can a Euclidean Traveling Salesman Tour Be?
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 1436138 (Why is no real title available?)
• On the complexity of approximating TSP with neighborhoods and related problems
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Reducing curse of dimensionality: improved PTAS for TSP (with neighborhoods) in doubling metrics
• The Euclidean traveling salesman problem is NP-complete

Cited in

(3)

• Minimum cycle partition with length requirements
• Geometric multicut: shortest fences for separating groups of objects in the plane
• On the shortest separating cycle

This page was built for publication: The shortest separating cycle problem

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