๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

The General Steiner Tree-Star problem

โœ Scribed by Samir Khuller; An Zhu


Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
78 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis


The Steiner tree problem is defined as follows-given a graph G = (V , E) and a subset X โŠ‚ V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a "switch" cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V \ X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of (ln n) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.


๐Ÿ“œ SIMILAR VOLUMES


The Steiner tree problem
โœ Dirk van Oudheusden ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 87 KB
The 1-steiner tree problem
โœ George Georgakopoulos; Christos H Papadimitriou ๐Ÿ“‚ Article ๐Ÿ“… 1987 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 480 KB
On the terminal Steiner tree problem
โœ Guohui Lin; Guoliang Xue ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 69 KB

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

A constrained Steiner tree problem
โœ Moshe B. Rosenwein; Richard T. Wong ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 645 KB