Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem

DOI10.1007/s40305-022-00437-1MaRDI QIDQ6601971

Wencheng Wang, Pengxiang Pan, Jianping Li, Suding Liu, Junran Lichen

Publication date: 11 September 2024

Published in: Journal of the Operations Research Society of China (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsSteiner ratio1-line minimum Steiner tree of line segmentsminimum spanning tree of line segmentsVoronoi diagram of line segments

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Planar bichromatic minimum spanning trees
• Steiner minimal trees
• A constrained minimum spanning tree problem
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• Minimum spanning tree of line segments
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computing Euclidean Steiner trees over segments
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• The Design of Approximation Algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An optimal minimum spanning tree algorithm
• Finding Least-Distances Lines
• Finding Minimum Spanning Trees
• 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
• Growing a Tree from Its Branches
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Steiner Minimal Trees
• Combinatorial optimization. Theory and algorithms.
• Steiner tree problems
• Solving Steiner trees: Recent advances, challenges, and perspectives

This page was built for publication: Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem