ECCC-Report TR95-003https://eccc.weizmann.ac.il/report/1995/003Comments and Revisions published for TR95-003en-usSun, 01 Jan 1995 00:00:00 +0200
Paper TR95-003
| 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems |
Marek Karpinski,
Alexander Zelikovsky
https://eccc.weizmann.ac.il/report/1995/003The Steiner tree problem requires to find a shortest tree connection
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.
Sun, 01 Jan 1995 00:00:00 +0200https://eccc.weizmann.ac.il/report/1995/003