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