Publication detail

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

ŠEDA, M.

Original 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

Czech

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.

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.

Key words in English

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

Authors

ŠEDA, M.

Released

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

154

Pages to

158

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