\(1\)-line minimum rectilinear Steiner trees and related problems
type: Item
instance of: scholarly article
title: \(1\)-line minimum rectilinear Steiner trees and related problems
zbMATH Open document ID: 1504.90128
author: Jianping Li
author: Junran Lichen
author: Wencheng Wang
author: Jean Yeh
author: Yeong-Nan Yeh
author: Xingxing Yu
author: Yujie Zheng
published in: Journal of Combinatorial Optimization
publication date: 2022-10-18T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 7603295
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: \(1\)-line minimum rectilinear Steiner tree
zbMATH Keywords: \(1\)-line-fixed-constrained minimum rectilinear Steiner tree
zbMATH Keywords: approximation algorithms
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: s10878-021-00796-0
OpenAlex ID: W3196792919
cites work: Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs
cites work: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
cites work: Q5452284
cites work: The Steiner problem with edge lengths 1 and 2
cites work: An improved LP-based approximation for Steiner tree
cites work: A constrained minimum spanning tree problem
cites work: Q3689203
cites work: Steiner minimal trees
cites work: The Complexity of Computing Steiner Minimal Trees
cites work: The 1-steiner tree problem
cites work: Steiner Minimal Trees
cites work: Q4691686
cites work: On Steiner Minimal Trees with Rectilinear Distance
cites work: An O ( n log n ) Algorithm for Rectilinear Minimal Spanning Trees
cites work: Steiner tree problems
cites work: Dynamic Steiner Tree Problem
cites work: The Rectilinear Steiner Tree Problem is $NP$-Complete
cites work: Combinatorial optimization. Theory and algorithms.
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem
cites work: Fast heuristic algorithms for rectilinear Steiner trees
cites work: A simple proof of the planar rectilinear Steiner ratio
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
cites work: The Design of Approximation Algorithms
cites work: On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
cites work: Efficient minimum spanning tree construction with Delaynay triangulation
DOI: 10.1007/S10878-021-00796-0
description: scientific article; zbMATH DE number 7603295