Detail publikačního výsledku

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

ŠEDA, M.

Originální název

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Anglický název

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Druh

Článek recenzovaný mimo WoS a Scopus

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

Klíčová slova v angličtině

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

Autoři

ŠEDA, M.

Vydáno

01.04.2005

ISSN

1109-2769

Periodikum

WSEAS Transactions on Mathematics

Svazek

4

Číslo

2

Stát

Řecká republika

Strany od

82

Strany počet

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