Publication detail

Solving Steiner Tree Problem Using Local Search Methods

ŠEDA, M.

Original Title

Solving Steiner Tree Problem Using Local Search Methods

Type

conference paper

Language

English

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.

Key words in English

network Steiner tree problem, enumeration methods, stochastic heuristics

Authors

ŠEDA, M.

Released

1. 9. 1999

Publisher

VUT FEI v Brně

Location

Brno

ISBN

80-214-1154-6

Book

Proceedings of the 22nd International Conference Telecommunications and Signal Processing TSP ‘99

Pages from

102

Pages to

105

Pages count

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",
  pages="4",
  publisher="VUT FEI v Brně",
  address="Brno",
  isbn="80-214-1154-6"
}