𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The full Steiner tree problem

✍ Scribed by Chin Lung Lu; Chuan Yi Tang; Richard Chia-Tung Lee

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
358 KB
Volume
306
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V; E) with a length function on E and a proper subset R βŠ‚ V , the problem is to ΓΏnd a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 8 5 -approximation algorithm to ΓΏnd an approximate solution for the problem.

πŸ“œ SIMILAR VOLUMES

The Steiner tree problem
The Steiner tree problem
✍ Dirk van Oudheusden πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 87 KB
Rectilinear full Steiner tree generation
Rectilinear full Steiner tree generation
✍ Zachariasen, Martin πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 353 KB

The fastest exact algorithm (in practice) for the rectilinear Steiner tree problem in the plane uses a two-phase scheme: First, a small but sufficient set of full Steiner trees (FSTs) is generated and then a Steiner minimum tree is constructed from this set by using simple backtrack search, dynamic

The 1-steiner tree problem
The 1-steiner tree problem
✍ George Georgakopoulos; Christos H Papadimitriou πŸ“‚ Article πŸ“… 1987 πŸ› Elsevier Science 🌐 English βš– 480 KB
On the terminal Steiner tree problem
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