✦ LIBER ✦

The internal Steiner tree problem: Hardness and approximations

✍ Scribed by Huang, Chao-Wen; Lee, Chia-Wei; Gao, Huang-Ming; Hsieh, Sun-Yuan

Book ID: 119291719
Publisher: Elsevier Science
Year: 2013
Tongue: English
Weight: 834 KB
Volume: 29
Category: Article
ISSN: 0885-064X
DOI: 10.1016/j.jco.2012.08.005

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Approximations for a Bottleneck Steiner

Approximations for a Bottleneck Steiner Tree Problem

✍ L. Wang and D. -Z. Du 📂 Article 📅 2002 🏛 Springer 🌐 English ⚖ 79 KB

Approximating the selected-internal Stei

Approximating the selected-internal Steiner tree

✍ Sun-Yuan Hsieh; Shih-Cheng Yang 📂 Article 📅 2007 🏛 Elsevier Science 🌐 English ⚖ 338 KB

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

Differential approximation results for t

Differential approximation results for the Steiner tree problem

✍ M Demange; J Monnot; V.Th Paschos 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 654 KB

we study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than IV \ Nj-' for any E E (0, l), where V and N are the vertex-set of the input graph and the set of term

The Steiner tree problem

✍ Dirk van Oudheusden 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 87 KB

Faster Approximation Algorithms for the

Faster Approximation Algorithms for the Rectilinear Steiner Tree Problem

✍ U. Fößmeier; M. Kaufmann; A. Zelikovsky 📂 Article 📅 1997 🏛 Springer 🌐 English ⚖ 217 KB