Further improvements of Steiner tree approximations

Karpinksi, M.; Zelikovsky, Alexander

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

報告書

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

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

MPI-I-94-158.pdf
(全文テキスト（全般）), 8MB

付随資料 (公開)

There is no public supplementary material available

引用

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

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

要旨

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.