Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
DOI10.1007/S10878-019-00492-0zbMATH Open1437.90139OpenAlexW2990586926WikidataQ126669554 ScholiaQ126669554MaRDI QIDQ2292156FDOQ2292156
Authors: Jianping Li, Suding Liu, Junran Lichen, Wencheng Wang, Yujie Zheng 
Publication date: 3 February 2020
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-019-00492-0
Recommendations
- On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
- \(1\)-line minimum rectilinear Steiner trees and related problems
- On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
- Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
- On the restricted \(k\)-Steiner tree problem
complexityapproximation algorithmsSteiner ratio1-line Euclidean minimum Steiner treeconstrained Euclidean minimum Steiner tree
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)
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Tighter Bounds for Graph Steiner Tree Approximation
- Computational geometry. Algorithms and applications.
- Combinatorial optimization. Theory and algorithms.
- Steiner Minimal Trees
- Steiner tree problems
- An improved LP-based approximation for Steiner tree
- 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
- Title not available (Why is that?)
- Steiner minimal trees
- The Steiner problem with edge lengths 1 and 2
- Title not available (Why is that?)
- A constrained minimum spanning tree problem
- Variations on the Euclidean Steiner tree problem and algorithms
- Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
Cited In (10)
- On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\)
- Computing Euclidean Steiner trees over segments
- On the restricted 1-Steiner tree problem
- Variations on the Euclidean Steiner tree problem and algorithms
- On the restricted \(k\)-Steiner tree problem
- Approximation algorithms for solving the 1-line minimum Steiner tree of line segments problem
- An exact algorithm for the line-constrained bottleneck \(k\)-Steiner tree problem
- On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\)
- Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
- \(1\)-line minimum rectilinear Steiner trees and related problems
This page was built for publication: Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2292156)
