Publication detail

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

ŠEDA, M.

Original Title

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

English Title

Applications of Steiner Trees in Network Optimization

Type

conference paper

Language

Czech

Original Abstract

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.

English abstract

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.

Key words in English

Steiner tree, spanning tree, stochastic heuristics

Authors

ŠEDA, M.

Released

1. 6. 2000

Publisher

Univerzita Pardubice

Location

Kouty na Desnou

ISBN

80-7194-271-5

Book

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

Pages from

53

Pages to

53

Pages count

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"
}