Steiner problems in graphs: Algorithms and Applications

L. R. Foulds; V. J. Rayward-Smith

doi:10.1080/03052158308960625

Steiner problems in graphs: Algorithms and Applications

L. R. Foulds, V. J. Rayward-Smith

School of Computing Sciences

Research output: Contribution to journal › Article › peer-review

16 Citations (Scopus)

Abstract

Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.

Original language	English
Pages (from-to)	7-16
Number of pages	10
Journal	Engineering Optimization
Volume	7
Issue number	1
DOIs	https://doi.org/10.1080/03052158308960625
Publication status	Published - 1983

Access to Document

10.1080/03052158308960625

Cite this

@article{95da7d93a0a946a7b50c9c6b4c17e345,

title = "Steiner problems in graphs: Algorithms and Applications",

abstract = "Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.",

author = "Foulds, {L. R.} and Rayward-Smith, {V. J.}",

year = "1983",

doi = "10.1080/03052158308960625",

language = "English",

volume = "7",

pages = "7--16",

journal = "Engineering Optimization",

issn = "0305-215X",

publisher = "Taylor and Francis",

number = "1",

}

TY - JOUR

T1 - Steiner problems in graphs: Algorithms and Applications

AU - Foulds, L. R.

AU - Rayward-Smith, V. J.

PY - 1983

Y1 - 1983

N2 - Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.

AB - Consider an undirected graph G = (V, E) with positive edge weights and a nonempty set S ? V, where Vand E are the sets of vertices and edges of G respectively. The Steiner problem in graphs is that of finding a subgraph of G which spans S and is of minimum total edge weight. In this paper we survey solution procedures for this problem. As the associated decision problem is NP-Complete we place special emphasis on heuristic methods of solution. We also examine special cases, related problems, and applications. The paper concludes with ideas for the development of new, efficient heuristics.

U2 - 10.1080/03052158308960625

DO - 10.1080/03052158308960625

M3 - Article

VL - 7

SP - 7

EP - 16

JO - Engineering Optimization

JF - Engineering Optimization

SN - 0305-215X

IS - 1

ER -