Detail publikace

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

ŠEDA, M.

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

čeština

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.

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

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

Autoři

ŠEDA, M.

Vydáno

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

Strany od

154

Strany do

158

Strany počet

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",
  pages="5",
  publisher="VŠB-TU Ostrava",
  address="Dolní Lomná u Jablunkova",
  isbn="80-7078-836-4"
}