Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Stochastické heuristické metody pro Steinerův problém v grafech

článek ve sborníku ve WoS nebo Scopus

abchazština

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