Detail publikačního výsledku

Solving Steiner Tree Problem Using Local Search Methods

ŠEDA, M.

Originální název

Solving Steiner Tree Problem Using Local Search Methods

Anglický název

Solving Steiner Tree Problem Using Local Search Methods

Druh

Stať ve sborníku v databázi WoS či Scopus

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.

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 v angličtině

Spanning tree, Steiner tree, approximate algorithms, stochastic heuristic techniques

Autoři

ŠEDA, M.

Vydáno

01.09.1999

Nakladatel

UTKO FEI VUT, EES

Místo

Brno, ČR

ISBN

80-214-1154-6

Kniha

Telecommunications and Signal processing - TST'99. 22nd Inte

Strany od

102

Strany do

105

Strany počet

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",
  pages="102--105",
  publisher="UTKO FEI VUT, EES",
  address="Brno, ČR",
  isbn="80-214-1154-6"
}