Eppstein?s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it

Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F01%3APU21352" target="_blank" >RIV/00216305:26210/01:PU21352 - isvavai.cz</a>
Výsledek na webu
—
DOI - Digital Object Identifier
—

Jazyk výsledku
angličtina
Název v původním jazyce
Eppstein?s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it
Popis výsledku v původním jazyce
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
Název v anglickém jazyce
Eppstein?s Proof of the Steiner Ratio for Rectilinear Steiner Trees is Mistaken and How to Correct it
Popis výsledku anglicky
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

Rok uplatnění
2001
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku
Proceedings of the 7th International Conference on Soft Computing MENDEL 2001
ISBN
80-214-1894-X
ISSN
—
e-ISSN
—
Počet stran výsledku
7
Strana od-do
221-227
Název nakladatele
VUT FSI v Brně
Místo vydání
Brno
Místo konání akce
Brno
Datum konání akce
6. 6. 2001
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—

Podobné výsledky(10)