Publication detail
Solving Steiner Tree Problem Using Local Search Methods
ŠEDA, M.
Czech title
Řešení Steinerova problému s vuzižitím lokálního hledání
English title
Solving Steiner Tree Problem Using Local Search Methods
Type
conference paper
Language
en
Original abstract
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.
English abstract
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.
Keywords in English
Spanning tree, Steiner tree, approximate algorithms, stochastic heuristic techniques
RIV year
1999
Released
01.09.1999
Publisher
UTKO FEI VUT, EES
Location
Brno, ČR
ISBN
80-214-1154-6
Book
Telecommunications and Signal processing - TST'99. 22nd Inte
Pages from–to
102–105
Pages count
4
BIBTEX
@inproceedings{BUT67,
author="Miloš {Šeda},
title="Solving Steiner Tree Problem Using Local Search Methods",
booktitle="Telecommunications and Signal processing - TST'99. 22nd Inte",
year="1999",
month="September",
pages="102--105",
publisher="UTKO FEI VUT, EES",
address="Brno, ČR",
isbn="80-214-1154-6"
}