Applications of Steiner Trees in Network Optimization
The result's identifiers
Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
čeština
Original language name
Aplikace Steinerových stromů v síťové optimalizaci
Original language description
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.
Czech name
Aplikace Steinerových stromů v síťové optimalizaci
Czech description
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.
Classification
Type
D - Article in proceedings
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2000
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 4th International Scientific-Technical Conference PROCESS CONTROL 2000 (ŘÍP 2000)
ISBN
80-7194-271-5
ISSN
—
e-ISSN
—
Number of pages
1
Pages from-to
53-53
Publisher name
Univerzita Pardubice
Place of publication
Kouty na Desnou
Event location
Kouty nad Desnou
Event date
Jun 11, 2000
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—