Detail publikace

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

ŠEDA, M.

Originální 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

čeština

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.

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 v angličtině

Steiner tree, spanning tree, stochastic heuristics

Autoři

ŠEDA, M.

Vydáno

1. 6. 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)

Strany od

53

Strany do

53

Strany počet

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",
  pages="1",
  publisher="Univerzita Pardubice",
  address="Kouty na Desnou",
  isbn="80-7194-271-5"
}