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