Detail publikačního výsledku

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

ŠEDA, M.

Originální 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

Druh

Stať ve sborníku v databázi WoS či Scopus

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 v angličtině

Steiner tree problem, stochastic heuristic methods, approximation methods

Autoři

ŠEDA, M.

Vydáno

01.07.2001

Nakladatel

Netherlands Society for Operations Research

Místo

Rotterdam

Kniha

Abstracts of the European Operational Research Conference EURO 2001

Strany od

74

Strany počet

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"
}