Detail publikace
Řešení Steinerova problému s využitím metod lokálního hledání
ŠEDA, M.
Český název
Řešení Steinerova problému s využitím metod lokálního hledání
Anglický název
Solving Steiner Tree Problem Using Local Search Methods
Typ
článek ve sborníku ve WoS nebo Scopus
Jazyk
en
Originální abstrakt
The Steiner tree problem (STP) on a graph involves finding a minimum cost tree which connects a designated subset of the nodes in the graph. This problem generalizes the minimum spanning tree problem and is more complicated since there are Steiner nodes which are not in the designated subset but may or may not be connected by the Steiner tree solution. Variants of the basic network Steiner tree model (Euclidean, rectilinear) can arise in the design of telecommunication networks where customers must be connected to a switching centre. The paper describes solution representations used in heuristic techniques for solving STP.
Český abstrakt
Steinerův problém v grafech spočívá v hledání stromu minimální celkové délky hran, který spojuje označenou podmnožimu vrcholů daného grafu. Tento problém je zobecněním problému hledání minimální kostry grafu a je mnohem složitější, protože řešení může obsahovat i vrcholy, které nebyly označeny. Euklidovská a rektilineární varianta základní grafové verze problému má aplikace v návrhu telekomunikačních sítí, jejíž vybraní účastníci mají být spojeni. Příspěvek popisuje reprezentace problému pro řešení heuristickými technikami.
Anglický abstrakt
The Steiner tree problem (STP) on a graph involves finding a minimum cost tree which connects a designated subset of the nodes in the graph. This problem generalizes the minimum spanning tree problem and is more complicated since there are Steiner nodes which are not in the designated subset but may or may not be connected by the Steiner tree solution. Variants of the basic network Steiner tree model (Euclidean, rectilinear) can arise in the design of telecommunication networks where customers must be connected to a switching centre. The paper describes solution representations used in heuristic techniques for solving STP.
Klíčová slova anglicky
network Steiner tree problem, enumeration methods, stochastic heuristics
Vydáno
01.09.1999
Nakladatel
VUT FEI v Brně
Místo
Brno
ISBN
80-214-1154-6
Kniha
Proceedings of the 22nd International Conference Telecommunications and Signal Processing TSP ‘99
Počet stran
4
BIBTEX
@inproceedings{BUT20811,
author="Miloš {Šeda},
title="Solving Steiner Tree Problem Using Local Search Methods",
booktitle="Proceedings of the 22nd International Conference Telecommunications and Signal Processing TSP ‘99",
year="1999",
month="September",
publisher="VUT FEI v Brně",
address="Brno",
isbn="80-214-1154-6"
}