Detail publikace
Eppstein’s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it
ŠEDA, M.
Anglický název
Eppstein’s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
In this paper, we deal with rectilinear Steiner trees and their approximation by a rectilinear minimum spanning tree. It is known that the approximation ratio (called Steiner ratio) equals 1.50. In literature, several different proofs of this assertion can be found. We show that David Eppstein's proof (presented in [Hochbaum, 1996]) is mistaken and propose its modification to prove the Steiner ratio correctly
Anglický abstrakt
In this paper, we deal with rectilinear Steiner trees and their approximation by a rectilinear minimum spanning tree. It is known that the approximation ratio (called Steiner ratio) equals 1.50. In literature, several different proofs of this assertion can be found. We show that David Eppstein's proof (presented in [Hochbaum, 1996]) is mistaken and propose its modification to prove the Steiner ratio correctly
Klíčová slova anglicky
rectilinear Steiner tree, rectilinear spanning tree, approximation, Steiner ratio
Rok RIV
2001
Vydáno
01.06.2001
Nakladatel
VUT FSI v Brně
Místo
Brno
ISBN
80-214-1894-X
Kniha
Proceedings of the 7th International Conference on Soft Computing MENDEL 2001
Počet stran
7
BIBTEX
@inproceedings{BUT6614,
author="Miloš {Šeda},
title="Eppstein’s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it",
booktitle="Proceedings of the 7th International Conference on Soft Computing MENDEL 2001",
year="2001",
month="June",
publisher="VUT FSI v Brně",
address="Brno",
isbn="80-214-1894-X"
}