Further improvements of Steiner tree approximations

Karpinksi, M.; Zelikovsky, Alexander

Datensatz

DATENSATZ AKTIONENEXPORT

Zur Ablage hinzufügen

Lokale TagsFreigabegeschichteDetailsÜbersicht

Freigegeben

Bericht

Further improvements of Steiner tree approximations

MPG-Autoren

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;

Externe Ressourcen

Es sind keine externen Ressourcen hinterlegt

Volltexte (beschränkter Zugriff)

Für Ihren IP-Bereich sind aktuell keine Volltexte freigegeben.

Volltexte (frei zugänglich)

MPI-I-94-158.pdf
(beliebiger Volltext), 8MB

Ergänzendes Material (frei zugänglich)

Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar

Zitation

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

Zitierlink: https://hdl.handle.net/11858/00-001M-0000-0014-B7A4-B

Zusammenfassung

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.