Detail publikace

Několik poznámek k důkazům Steinerova poměru pro rektilineární Steinerovy stromy

ŠEDA, M.

Český název

Několik poznámek k důkazům Steinerova poměru pro rektilineární Steinerovy stromy

Anglický název

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Typ

článek v časopise - ostatní, Jost

Jazyk

en

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.

Český abstrakt

V příspěvku se zabýváme rektilineárními Steinerovy stromy a jejich aproximací rektilineární kostrou grafu. Je známo, že aproximační poměr této aproximace (nazývaný Steinerův poměr) je roven 1.50. V literatuře lze najít několik odlišných důkazů tohoto tvrzení. Ukážeme zde, že důkaz prezentovaný v [7] je chybný a dále, jak jej třeba modifikovat, aby byl korektní.

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 anglicky

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

Rok RIV

2005

Vydáno

01.04.2005

ISSN

1109-2769

Časopis

WSEAS Transactions on Mathematics

Ročník

4

Číslo

2

Počet stran

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",
  month="April",
  issn="1109-2769"
}