The Steiner problem in graphs
SE Dreyfus, RA Wagner - Networks, 1971 - Wiley Online Library
SE Dreyfus, RA Wagner
Networks, 1971•Wiley Online LibraryAn 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 n3/2+ n2 (2k‐1‐k‐1)+ n (3k‐1‐2k+ 3)/2. The time requirement above
includes the term n3/2, which can be eliminated if the set of shortest paths connecting each
pair of nodes in the graph is available.
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 n3/2+ n2 (2k‐1‐k‐1)+ n (3k‐1‐2k+ 3)/2. The time requirement above
includes the term n3/2, which can be eliminated if the set of shortest paths connecting each
pair of nodes in the graph is available.
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 n3/2 + n2 (2k‐1 ‐ k ‐ 1) + n(3k‐1 ‐ 2k + 3)/2.
The time requirement above includes the term n3/2, which can be eliminated if the set of shortest paths connecting each pair of nodes in the graph is available.
Wiley Online Library