Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

conference paper

Abkhaz

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.

Steiner tree problem, stochastic heuristic methods, approximation methods

ŠEDA, M.

2001

1. 7. 2001

Netherlands Society for Operations Research

Rotterdam

74

74

1