Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
DOI10.1007/S40305-022-00437-1MaRDI QIDQ6601971FDOQ6601971
Authors: Jianping Li, Suding Liu, Junran Lichen, Pengxiang Pan, Wencheng Wang 
Publication date: 11 September 2024
Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)
approximation algorithmsSteiner ratio1-line minimum Steiner tree of line segmentsminimum spanning tree of line segmentsVoronoi diagram of line segments
Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
- On the shortest spanning subtree of a graph and the traveling salesman problem
- The design of approximation algorithms
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Tighter Bounds for Graph Steiner Tree Approximation
- Steiner tree approximation via iterative randomized rounding
- Computational geometry. Algorithms and applications.
- Combinatorial optimization. Theory and algorithms.
- Steiner Minimal Trees
- Steiner tree problems
- The Complexity of Computing Steiner Minimal Trees
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Steiner minimal trees
- An optimal minimum spanning tree algorithm
- Finding Minimum Spanning Trees
- Planar bichromatic minimum spanning trees
- Finding Least-Distances Lines
- Title not available (Why is that?)
- Growing a Tree from Its Branches
- A constrained minimum spanning tree problem
- Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
- Variations on the Euclidean Steiner tree problem and algorithms
- Solving Steiner trees: Recent advances, challenges, and perspectives
- Minimum spanning tree of line segments
- Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
- Computing Euclidean Steiner trees over segments
This page was built for publication: Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6601971)
