Publication detail

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

ŠEDA, M.

Original Title

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

Type

conference paper

Language

English

Original Abstract

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

Key words in English

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

Authors

ŠEDA, M.

RIV year

2001

Released

1. 6. 2001

Publisher

VUT FSI v Brně

Location

Brno

ISBN

80-214-1894-X

Book

Proceedings of the 7th International Conference on Soft Computing MENDEL 2001

Pages from

221

Pages to

227

Pages count

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"
}