Detail publikace

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

ŠEDA, M.

Český název

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Anglický název

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Typ

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

Jazyk

ab

Anglický abstrakt

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.

Klíčová slova anglicky

Steiner tree problem, stochastic heuristic methods, approximation methods

Rok RIV

2001

Vydáno

01.07.2001

Nakladatel

Netherlands Society for Operations Research

Místo

Rotterdam

Kniha

Abstracts of the European Operational Research Conference EURO 2001

Počet stran

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",
  month="July",
  publisher="Netherlands Society for Operations Research",
  address="Rotterdam"
}