The steiner problem in graphs

Stuart E. Dreyfus, Robert A. Wagner

Networks · 1971 · 693 citations · 2 references

Concepts

Abstract

Abstract An algorithm for solving the Steiner problem on a finite undirected graph is presented. This algorithm computes the set of graph arcs of minimum total length needed to connect a specified set of k graph nodes. If the entire graph contains n nodes, the algorithm requires time proportional to n 3 /2 + n 2 (2 k‐1 ‐ k ‐ 1) + n(3 k‐1 ‐ 2 k + 3)/2. The time requirement above includes the term n 3 /2, which can be eliminated if the set of shortest paths connecting each pair of nodes in the graph is available.

References

2