Aplikace Steinerových stromů v síťové optimalizaci

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F00%3APU56192" target="_blank" >RIV/00216305:26210/00:PU56192 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Aplikace Steinerových stromů v síťové optimalizaci

Popis výsledku v původním jazyce

Steinerův problém v grafech reprezentuje hledání stromu minimální ceny, který spojuje definovanou podmnožinu vrcholů grafu. Tento problém zobecňuje problém minimální kostry grafu, je však mnohem složitější, protože řešení může obsahovat i vrcholy, kterénepatří do základní množiny vrcholů. Zatímco pro řešení problému minimální kostry existují jednoduché algoritmy polynomiální složitosti, Steinerův problém v grafech patří mezi tzv. NP-těžké problémy a jeho přesné řešení pro úlohy většího rozsahu nelze zíískat v reálném čase. Steinerův problém v grafech a jeho varianty (Steinerův problém v euklidovské rovině a rektilineární Steinerův problém) mají řadu praktických aplikací, např. v návrhu telekomunikačních sítí, v návrhu VLSI obvodů a v některých speciálních úlohách (multicast routing, file replication problem). Příspěvek se zabývá řešením problému pomocí stochastických heuristických metod.

Název v anglickém jazyce

Applications of Steiner Trees in Network Optimization

Popis výsledku anglicky

Steiner tree problem in graphs represents searching of minimal tree that connects a given subset of graph vertices. This problem generalises the minimum spanning tree problem but it is much more complicated because its solution can include also additional vertices that do not belong into the given set of vertices. While there are simple polynomial algorithms for solving minimum spanning tree problem, Steiner tree problem in graphs and its modifications (Steiner tree problem in the Euclidean plane and reectilinear Steiner tree problem) have many practical applications, e.g. in design of telecommunication networks, VLSI design and special tasks such as multicast routing and file replication problem. This paper deals with solving the problem using stochastic heuristic methods.

Druh

D - Stať ve sborníku

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í

2000

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 statě ve sborníku

Proceedings of the 4th International Scientific-Technical Conference PROCESS CONTROL 2000 (ŘÍP 2000)

ISBN

80-7194-271-5

ISSN

—

e-ISSN

—

Počet stran výsledku

1

Strana od-do

53-53

Název nakladatele

Univerzita Pardubice

Místo vydání

Kouty na Desnou

Místo konání akce

Kouty nad Desnou

Datum konání akce

11. 6. 2000

Typ akce podle státní příslušnosti

EUR - Evropská akce

Kód UT WoS článku

—