Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F01%3APU23161" target="_blank" >RIV/00216305:26210/01:PU23161 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

čeština

Název v původním jazyce

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Popis výsledku v původním jazyce

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 aa 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-l

Název v anglickém jazyce

Stochastic Heuristic Methods for the Steiner Tree Problem in Graphs

Popis výsledku anglicky

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 aa 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-l

Druh

D - Stať ve sborníku

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2001

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Abstracts of the European Operational Research Conference EURO 2001

ISBN

—

ISSN

—

e-ISSN

—

Počet stran výsledku

1

Strana od-do

74-74

Název nakladatele

Netherlands Society for Operations Research

Místo vydání

Rotterdam

Místo konání akce

Rotterdam

Datum konání akce

9. 7. 2001

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—