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

DOI10.1007/s10878-019-00492-0zbMath1437.90139OpenAlexW2990586926WikidataQ126669554 ScholiaQ126669554MaRDI QIDQ2292156

Wencheng Wang, Yujie Zheng, Junran Lichen, Jianping Li, Suding Liu

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

zbMATH Keywords

complexityapproximation algorithmsSteiner ratio1-line Euclidean minimum Steiner treeconstrained Euclidean minimum Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (5)

On the minimum number of Steiner points of constrained 1-line-fixed Steiner tree in the Euclidean plane \(\mathbb{R}^2\) ⋮ On the restricted 1-Steiner tree problem ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• The Steiner problem with edge lengths 1 and 2
• Steiner minimal trees
• A constrained minimum spanning tree problem
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
• An improved LP-based approximation for steiner tree
• The Design of Approximation Algorithms
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• 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
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Minimal Trees
• Combinatorial optimization. Theory and algorithms.
• Steiner tree problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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