English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Further improvements of Steiner tree approximations

MPS-Authors

Karpinksi,  M.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45793

Zelikovsky,  Alexander
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

MPI-I-94-158.pdf
(Any fulltext), 8MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Karpinksi, M., & Zelikovsky, A.(1994). Further improvements of Steiner tree approximations (MPI-I-94-158). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B7A4-B
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.