1971/01/01 by Stuart E. Dreyfus, Robert A. Wagner · 8 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Advanced Graph Theory Research #Combinatorics #Graph #Mathematics #Undirected graph #Discrete mathematics #Computer science
paper · doi:10.1002/net.3230010302
openalex publication_date 1971/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/25
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.