On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane R^2

DOI10.1007/978-3-030-57602-8_5MaRDI QIDQ2039643zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

complexityapproximation algorithms1-line minimum rectilinear Steiner treeconstrained minimum rectilinear Steiner tree

Mathematics Subject Classification ID

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)

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

Cites work

• An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Computational geometry. Algorithms and applications.
• Dynamic Steiner Tree Problem
• Efficient minimum spanning tree construction with Delaynay triangulation
• Fast heuristic algorithms for rectilinear Steiner trees
• On Steiner Minimal Trees with Rectilinear Distance
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Steiner tree problems
• The Complexity of Computing Steiner Minimal Trees
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Steiner problem with edge lengths 1 and 2
• The design of approximation algorithms
• Variations on the Euclidean Steiner tree problem and algorithms

Cited in

(5)

• On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
• \(1\)-line minimum rectilinear Steiner trees and related problems
• Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• Approximations for two variants of the Steiner tree problem in the Euclidean plane \(\mathbb R^2\)

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)