Publication detail
Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees
ŠEDA, M.
Czech title
Několik poznámek k důkazům Steinerova poměru pro rektilineární Steinerovy stromy
English title
Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees
Type
journal article - other
Language
en
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.
Czech abstract
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í.
English 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.
Keywords in English
rectilinear metric, Steiner tree, spanning tree, approximation, Steiner ratio
RIV year
2005
Released
01.04.2005
ISSN
1109-2769
Journal
WSEAS Transactions on Mathematics
Volume
4
Number
2
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",
month="April",
issn="1109-2769"
}