\(1\)-line minimum rectilinear Steiner trees and related problems

DOI10.1007/s10878-021-00796-0zbMath1504.90128OpenAlexW3196792919MaRDI QIDQ2084647

Xingxing Yu, Wencheng Wang, Yeong-Nan Yeh, Jean Yeh, Junran Lichen, Jianping Li, Yujie Zheng

Publication date: 18 October 2022

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-021-00796-0

zbMATH Keywords

complexitycombinatorial optimizationapproximation algorithms\(1\)-line minimum rectilinear Steiner tree\(1\)-line-fixed-constrained minimum rectilinear Steiner tree

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• 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
• A simple proof of the planar rectilinear Steiner ratio
• Steiner minimal trees
• A constrained minimum spanning tree problem
• Efficient minimum spanning tree construction with Delaynay triangulation
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
• 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 1-steiner tree problem
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• 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 Minimal Trees
• Combinatorial optimization. Theory and algorithms.
• Steiner tree problems

This page was built for publication: \(1\)-line minimum rectilinear Steiner trees and related problems