Detail publikace
Aplikace Steinerových stromů v síťové optimalizaci
ŠEDA, M.
Český název
Aplikace Steinerových stromů v síťové optimalizaci
Anglický název
Applications of Steiner Trees in Network Optimization
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
cs
Originální abstrakt
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.
Český abstrakt
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.
Anglický abstrakt
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 rectilinear 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.
Klíčová slova anglicky
Steiner tree, spanning tree, stochastic heuristics
Vydáno
01.06.2000
Nakladatel
Univerzita Pardubice
Místo
Kouty na Desnou
ISBN
80-7194-271-5
Kniha
Proceedings of the 4th International Scientific-Technical Conference PROCESS CONTROL 2000 (ŘÍP 2000)
Počet stran
1
BIBTEX
@inproceedings{BUT21012,
author="Miloš {Šeda},
title="Aplikace Steinerových stromů v síťové optimalizaci",
booktitle="Proceedings of the 4th International Scientific-Technical Conference PROCESS CONTROL 2000 (ŘÍP 2000)",
year="2000",
month="June",
publisher="Univerzita Pardubice",
address="Kouty na Desnou",
isbn="80-7194-271-5"
}