Publication Details
Title: 1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems
Author: M. Karpinski and A. Zelikovsky
Group: ICSI Technical Reports
Date: March 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-010.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-95-010
Bibliographic Reference:
M. Karpinski and A. Zelikovsky. 1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems. ICSI Technical Report TR-95-010, March 1995
Author: M. Karpinski and A. Zelikovsky
Group: ICSI Technical Reports
Date: March 1995
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1995/tr-95-010.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-95-010
Bibliographic Reference:
M. Karpinski and A. Zelikovsky. 1.757 and 1.267-Approximation Algorithms for the Network and Rectilinear Steiner Tree Problems. ICSI Technical Report TR-95-010, March 1995