On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane R^2
DOI10.1007/978-3-030-57602-8_5zbMATH Open1482.68255OpenAlexW3047986206MaRDI QIDQ2039643FDOQ2039643
Authors: Junran Lichen, Jianping Li, Wencheng Wang, Jean Yeh, Yeong-Nan Yeh, Xingxing Yu, Yujie Zheng 
Publication date: 5 July 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-57602-8_5
Recommendations
- \(1\)-line minimum rectilinear Steiner trees and related problems
- Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
- On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
- A practical algorithm for the minimum rectilinear Steiner tree
- scientific article; zbMATH DE number 426374
complexityapproximation algorithms1-line minimum rectilinear Steiner treeconstrained minimum rectilinear Steiner tree
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Cites Work
- 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)
- Computational geometry. Algorithms and applications.
- Dynamic Steiner Tree Problem
- Steiner tree problems
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Complexity of Computing Steiner Minimal Trees
- The Steiner problem with edge lengths 1 and 2
- Efficient minimum spanning tree construction with Delaynay triangulation
- On Steiner Minimal Trees with Rectilinear Distance
- An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
- Variations on the Euclidean Steiner tree problem and algorithms
- Fast heuristic algorithms for rectilinear Steiner trees
Cited In (4)
- On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
- Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)
- Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
- \(1\)-line minimum rectilinear Steiner trees and related problems
This page was built for publication: On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2039643)
