On the terminal Steiner tree problem.

DOI10.1016/S0020-0190(02)00227-2zbMath1042.68094OpenAlexW1992573093MaRDI QIDQ1853109

Guoliang Xue, Guo-Hui Lin

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(02)00227-2

zbMATH Keywords

Steiner minimum treeApproximation algorithmsTerminal Steiner tree

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the terminal connection problem, DIAMETER-CONSTRAINED STEINER TREES, A better constant-factor approximation for selected-internal Steiner minimum tree, On some network design problems with degree constraints, On the computational difficulty of the terminal connection problem, On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems, A polylogarithmic approximation for computing non-metric terminal Steiner trees, Minimum diameter cost-constrained Steiner trees, An Efficient Approximation Algorithm for the Steiner Tree Problem, Algorithms for the minimum diameter terminal Steiner tree problem, On the hardness of full Steiner tree problems, The Bursty Steiner Tree Problem, Algorithms for terminal Steiner trees, The Euclidean bottleneck full Steiner tree problem, A note on the terminal Steiner tree problem, A multivariate analysis of the strict terminal connection problem, On approximation algorithms for the terminal Steiner tree problem, On the Clustered Steiner Tree Problem, On full Steiner trees in unit disk graphs, On the clustered Steiner tree problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• Optimization, approximation, and complexity classes
• On component-size bounded Steiner trees
• An 11/6-approximation algorithm for the network Steiner problem
• Faster exact algorithms for steiner trees in planar networks
• Improved Approximations for the Steiner Tree Problem
• Thek-Steiner Ratio in Graphs