On the terminal Steiner tree problem.
type: Item
instance of: scholarly article
title: On the terminal Steiner tree problem.
zbMATH Open document ID: 1042.68094
DOI: 10.1016/S0020-0190(02)00227-2
author: Guoliang Xue
author: Guohui Lin
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856446
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Steiner minimum tree
zbMATH Keywords: Terminal Steiner tree
MaRDI profile type: Publication
cites work: Improved Approximations for the Steiner Tree Problem
cites work: Faster exact algorithms for steiner trees in planar networks
cites work: The Steiner problem with edge lengths 1 and 2
cites work: Thek-Steiner Ratio in Graphs
cites work: On component-size bounded Steiner trees
cites work: Q4252319
cites work: Q4142699
cites work: Optimization, approximation, and complexity classes
cites work: Q4952699
cites work: An 11/6-approximation algorithm for the network Steiner problem
full work available at URL: s0020-0190(02)00227-2
OpenAlex ID: W1992573093
Recommended article: A note on the terminal Steiner tree problem
Recommended article: On approximation algorithms for the terminal Steiner tree problem
Recommended article: On the approximability of the Steiner tree problem.
Recommended article: Q5237808
Recommended article: Computing and Combinatorics
Recommended article: Algorithms for terminal Steiner trees
Recommended article: Q4400842
Recommended article: Q4779183
description: scientific article; zbMATH DE number 1856446