On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
DOI10.1007/978-3-030-57602-8_5zbMath1482.68255OpenAlexW3047986206MaRDI QIDQ2039643
Junran Lichen, Yeong-Nan Yeh, Xingxing Yu, Wencheng Wang, Jianping Li, Yujie Zheng, Jean Yeh
Publication date: 5 July 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_5
complexityapproximation algorithms1-line minimum rectilinear Steiner treeconstrained minimum rectilinear Steiner tree
Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Fast heuristic algorithms for rectilinear Steiner trees
- The Steiner problem with edge lengths 1 and 2
- Efficient minimum spanning tree construction with Delaynay triangulation
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- The Design of Approximation Algorithms
- Dynamic Steiner Tree Problem
- On Steiner Minimal Trees with Rectilinear Distance
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Complexity of Computing Steiner Minimal Trees
- Steiner tree problems
This page was built for publication: On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
