Detail publikace

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

ŠEDA, M.

Originální 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

angličtina

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

Klíčová slova v angličtině

rectilinear Steiner tree, rectilinear spanning tree, approximation, Steiner ratio

Autoři

ŠEDA, M.

Rok RIV

2001

Vydáno

1. 6. 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

Strany od

221

Strany do

227

Strany počet

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",
  pages="7",
  publisher="VUT FSI v Brně",
  address="Brno",
  isbn="80-214-1894-X"
}