Key points are not available for this paper at this time.
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.
Dreyfus et al. (Fri,) studied this question.