• search hit 20 of 28
Back to Result List

On approximation algorithms for the terminal Steiner tree problem

Please always quote using this URN:urn:nbn:de:0296-matheon-2812
  • The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2 , where denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of +2.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Doratha E. Drake, Stefan Hougardy
URN:urn:nbn:de:0296-matheon-2812
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:275
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.