Publication detail

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

ŠEDA, M.

Original Title

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Type

journal article - other

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 the proof presented in [7] is mistaken and propose its modification to prove the Steiner ratio correctly.

Key words in English

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

Authors

ŠEDA, M.

RIV year

2005

Released

1. 4. 2005

ISBN

1109-2769

Periodical

WSEAS Transactions on Mathematics

Year of study

4

Number

2

State

Hellenic Republic

Pages from

82

Pages to

88

Pages count

7

BibTex

@article{BUT42792,
  author="Miloš {Šeda}",
  title="Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees",
  journal="WSEAS Transactions on Mathematics",
  year="2005",
  volume="4",
  number="2",
  pages="7",
  issn="1109-2769"
}