𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Conversion of the Steiner Problem on the Euclidean Plane to the Steiner Problem on Graph

✍ Scribed by D. T. Lotarev; A. P. Uzdemir

Publisher
SP MAIK Nauka/Interperiodica
Year
2005
Tongue
English
Weight
158 KB
Volume
66
Category
Article
ISSN
0005-1179

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

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

On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisΓΏability of linear equation modulo 2. The improvement on the

Some generalizations of the steiner prob
Some generalizations of the steiner problem in graphs
✍ C. W. Duin; A. Volgenant πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 562 KB

The Steiner Problem in Graphs (SP) is the problem of finding a set of edges with minimum total weight which connects a given subset of nodes in an edge-weighted (undirected) graph. In the more general Node-weighted Steiner Problem (NSP) also node weights are considered. A restricted minimum spanning