✦ LIBER ✦

On the Steiner median of a tree

✍ Scribed by Lowell W. Beineke; Ortrud R. Oellermann; Raymond E. Pippert

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 639 KB
Volume: 68
Category: Article
ISSN: 0166-218X
DOI: 10.1016/0166-218x(95)00069-4

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

On Steiner centers and Steiner medians o

On Steiner centers and Steiner medians of graphs

✍ Oellermann, Ortrud R. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 Յ n Յ ͉V(G)

A note on Steiner tree games

✍ Darko Skorin-Kapov; Jadranka Skorin-Kapov 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 202 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 note on the terminal Steiner tree prob

A note on the terminal Steiner tree problem

✍ Bernhard Fuchs 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 53 KB

In 2002, Lin and Xue [Inform. Process. Lett. 84 (2002) 103-107] introduced a variant of the graph Steiner tree problem, in which each terminal vertex is required to be a leaf in the solution Steiner tree. They presented a ρ + 2 approximation algorithm, where ρ is the approximation ratio of the bes

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

On the location of Steiner points in uni

On the location of Steiner points in uniformly-oriented Steiner trees

✍ Benny K. Nielsen; Pawel Winter; Martin Zachariasen 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 84 KB