Detail publikace

Aproximativní a heuristické algoritmy pro řešení Steinerova problému

ŠEDA, M.

Český název

Aproximativní a heuristické algoritmy pro řešení Steinerova problému

Anglický název

Approximate and Heuristic Algorithms for Solving Steiner Tree Problem

Typ

článek ve sborníku ve WoS nebo Scopus

Jazyk

cs

Originální abstrakt

Steinerův problém v grafech a jeho geometrické varianty rektilineární a euklidovský Steinerův problém patří mezi NP-úplné problémy síťové optimalizace. Příspěvek shrnuje typické přístupy přibližného řešení problémů vycházející z aproximace minimální kostrou a problémově orientovaných heuristik.

Český abstrakt

Steinerův problém v grafech a jeho geometrické varianty rektilineární a euklidovský Steinerův problém patří mezi NP-úplné problémy síťové optimalizace. Příspěvek shrnuje typické přístupy přibližného řešení problémů vycházející z aproximace minimální kostrou a problémově orientovaných heuristik.

Anglický abstrakt

Steiner tree problem in graphs and its geometric modifications rectilinear and Euclidean Steiner tree problems belong to NP-complete problems network optimisation. This paper summarises typical approaches of approximate solutions of these problems outgoing from approximation by minimum spanning tree and problem-oriented heuristics.

Klíčová slova anglicky

spanning tree, Steiner tree, Steiner ratio, heuristic, aproximate algorithm

Vydáno

01.12.2000

Nakladatel

VŠB-TU Ostrava

Místo

Dolní Lomná u Jablunkova

ISBN

80-7078-836-4

Kniha

Sborník z 9. semináře Moderní matematické metody v inženýrství 3mi

Počet stran

5

BIBTEX


@inproceedings{BUT21010,
  author="Miloš {Šeda},
  title="Aproximativní a heuristické algoritmy pro řešení Steinerova problému",
  booktitle="Sborník z 9. semináře Moderní matematické metody v inženýrství 3mi",
  year="2000",
  month="December",
  publisher="VŠB-TU Ostrava",
  address="Dolní Lomná u Jablunkova",
  isbn="80-7078-836-4"
}