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

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

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ů

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

—