Několik poznámek k důkazům Steinerova poměru pro rektilineární Steinerovy stromy
Popis výsledku
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í.
Klíčová slova
rectilinear metricSteiner treespanning treeapproximationSteiner ratio
Identifikátory výsledku
Kód výsledku v IS VaVaI
Výsledek na webu
—
DOI - Digital Object Identifier
—
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
Some Remarks to Proofs of Steiner Ratio for Rectilinear Steiner Trees
Popis výsledku anglicky
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.
Klasifikace
Druh
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BB - Aplikovaná statistika, operační výzkum
OECD FORD obor
—
Návaznosti výsledku
Projekt
—
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2005
Kód důvěrnosti údajů
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Údaje specifické pro druh výsledku
Název periodika
WSEAS Transactions on Mathematics
ISSN
1109-2769
e-ISSN
—
Svazek periodika
4
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
GR - Řecká republika
Počet stran výsledku
7
Strana od-do
82-88
Kód UT WoS článku
—
EID výsledku v databázi Scopus
—
Základní informace
Druh výsledku
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP
BB - Aplikovaná statistika, operační výzkum
Rok uplatnění
2005