Publication result detail

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

ŠEDA, M.

Original Title

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

English Title

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Type

Paper in proceedings (conference paper)

English abstract

The Steiner tree problem in graphs (SPG) is concerned with connecting a subset of vertices at minimal cost. More precisely, given an undirected connected graph G=(V,E) with vertex set V, edge set E, nonnegative weights associated with the edges, and a subset B of V (called customer vertices or terminals), the problem is to find a subgraph, T, which connects the vertices in B so that the sum of the weights of the edges in T is minimized. It is obvious that the solution is always a tree and it is called a minimal Steiner tree for B in G. Applications of the SPG are frequently found in the layout of connection structures in networks and circuit design. Their common feature is that of connecting together a set of terminals (communications sites or circuits components) by a network of minimal total length. The contribution presents an application of stochastic heuristic methods in a combination with approximate algorithms and compares their effectiveness using standard benchmarks from OR-library.

Key words in English

Steiner tree problem, stochastic heuristic methods, approximation methods

Authors

ŠEDA, M.

Released

01.07.2001

Publisher

Netherlands Society for Operations Research

Location

Rotterdam

Book

Abstracts of the European Operational Research Conference EURO 2001

Pages from

74

Pages count

1

BibTex

@inproceedings{BUT6531,
  author="Miloš {Šeda}",
  title="Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs",
  booktitle="Abstracts of the European Operational Research Conference EURO 2001",
  year="2001",
  pages="1",
  publisher="Netherlands Society for Operations Research",
  address="Rotterdam"
}