Publication detail

Approximate and Heuristic Algorithms for Solving Steiner Tree Problem

ŠEDA, M.

Czech title

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

English title

Approximate and Heuristic Algorithms for Solving Steiner Tree Problem

Type

conference paper

Language

cs

Original abstract

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.

Czech abstract

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.

English abstract

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.

Keywords in English

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

Released

01.12.2000

Publisher

VŠB-TU Ostrava

Location

Dolní Lomná u Jablunkova

ISBN

80-7078-836-4

Book

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

Pages count

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