On the terminal Steiner tree problem.

DOI10.1016/S0020-0190(02)00227-2MaRDI QIDQ1853109zbMATH OpenOpenAlexFDO

Authors Guoliang Xue, Guohui 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

Approximation algorithmsSteiner minimum treeTerminal Steiner tree

Mathematics Subject Classification ID

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

Review text

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio \(\rho+2\), where \(\rho\) is the best-known approximation ratio for the graph Steiner tree problem.

Recommendations

• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• On the approximability of the Steiner tree problem.
• Approximation algorithms for the terminal Steiner tree problem
• Computing and Combinatorics
• Algorithms for terminal Steiner trees
• scientific article; zbMATH DE number 1182759
• scientific article; zbMATH DE number 1834686

Cites work

• An 11/6-approximation algorithm for the network Steiner problem
• Faster exact algorithms for steiner trees in planar networks
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 1305435 (Why is no real title available?)
• scientific article; zbMATH DE number 1445376 (Why is no real title available?)
• Improved Approximations for the Steiner Tree Problem
• On component-size bounded Steiner trees
• Optimization, approximation, and complexity classes
• The Steiner problem with edge lengths 1 and 2
• Thek-Steiner Ratio in Graphs

Cited in

(24)

• A note on the terminal Steiner tree problem
• On approximation algorithms for the terminal Steiner tree problem
• The Steiner tree problem for terminals on the boundary of a rectilinear polygon
• The Euclidean bottleneck full Steiner tree problem
• A multivariate analysis of the strict terminal connection problem
• On full Steiner trees in unit disk graphs
• On the clustered Steiner tree problem
• Minimum diameter cost-constrained Steiner trees
• Algorithms for terminal Steiner trees
• On the clustered Steiner tree problem
• Diameter-constrained Steiner trees
• An Efficient Approximation Algorithm for the Steiner Tree Problem
• On some network design problems with degree constraints
• A polylogarithmic approximation for computing non-metric terminal Steiner trees
• The bursty Steiner tree problem
• Algorithms for the minimum diameter terminal Steiner tree problem
• On the hardness of full Steiner tree problems
• Approximation algorithms for the terminal Steiner tree problem
• Computing and Combinatorics
• On the computational difficulty of the terminal connection problem
• On undirected two‐commodity integral flow, disjoint paths and strict terminal connection problems
• Multi-qubit lattice surgery scheduling
• On the terminal connection problem
• A better constant-factor approximation for selected-internal Steiner minimum tree

This page was built for publication: On the terminal Steiner tree problem.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853109)