1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems

Title1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems
Publication TypeTechnical Report
Year of Publication1995
AuthorsKarpinski, M., & Zelikovsky A.
Other Numbers950
Abstract

The Steiner tree problem requires to find a shortest tree connecting a given set of terminal points in a metric space. We suggest a better and fast heuristic for the Steiner problem in graphs and in rectilinear plane. This heuristic finds a Steiner tree at most 1.757 and 1.267 times longer than the optimal solution in graphs and rectilinear plane, respectively.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-010.pdf
Bibliographic Notes

ICSI Technical Report TR-95-010

Abbreviated Authors

M. Karpinski and A. Zelikovsky

ICSI Publication Type

Technical Report