Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F05%3APU53772" target="_blank" >RIV/00216305:26210/05:PU53772 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees

Original language description

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 name

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

Czech description

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í.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BB - Applied statistics, operational research

OECD FORD branch

—

Project

—

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2005

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

WSEAS Transactions on Mathematics

ISSN

1109-2769

e-ISSN

—

Volume of the periodical

4

Issue of the periodical within the volume

2

Country of publishing house

GR - GREECE

Number of pages

7

Pages from-to

82-88

UT code for WoS article

—

EID of the result in the Scopus database

—