✦ LIBER ✦

Some generalizations of the steiner problem in graphs

✍ Scribed by C. W. Duin; A. Volgenant

Publisher: John Wiley and Sons
Year: 1987
Tongue: English
Weight: 562 KB
Volume: 17
Category: Article
ISSN: 0028-3045
DOI: 10.1002/net.3230170309

No coin nor oath required. For personal study only.

✦ Synopsis

The Steiner Problem in Graphs (SP) is the problem of finding a set of edges with minimum total weight which connects a given subset of nodes in an edge-weighted (undirected) graph. In the more general Node-weighted Steiner Problem (NSP) also node weights are considered. A restricted minimum spanning tree model is adjusted for the NSP as well as for the Steiner Forest Problem, a newly introduced generaliza'tion. The NSP is related to the Directed Steiner Problem. Reduction tests for the SP, reducing the size of the problem graph, are adapted for these generalizations and some new tests are developed.

📜 SIMILAR VOLUMES

The steiner problem in graphs

✍ S. E. Dreyfus; R. A. Wagner 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 567 KB

Tabu search for the Steiner problem in g

Tabu search for the Steiner problem in graphs

✍ Celso C. Ribeiro; Maurício C. De Souza 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB 👁 2 views

Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum-weighted subgraph spanning a given subset of nodes (terminals) of the original graph. In this paper, we describe a tabu search algorithm for the Steiner problem in graphs, based o

An algorithm for the steiner problem in

An algorithm for the steiner problem in graphs

✍ M. L. Shore; L. R. Foulds; P. B. Gibbons 📂 Article 📅 1982 🏛 John Wiley and Sons 🌐 English ⚖ 528 KB

An algorithm for the steiner problem in

An algorithm for the steiner problem in graphs

✍ J. E. Beasley 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 579 KB

Steiner's problem in graphs and its impl

Steiner's problem in graphs and its implications

✍ S. L. Hakimi 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 952 KB

An SST-based algorithm for the steiner p

An SST-based algorithm for the steiner problem in graphs

✍ J. E. Beasley 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 644 KB

In this paper we consider the Steiner problem in graphs which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph. We present a formulation of the problem as a shortest spanning tree (SST) problem with additional constraints. By relaxing these addition