Networks · 1971 · 693 citations · 2 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsOptimizationCombinatorial OptimizationGraph AlgorithmsGraph TheoryShortest Path AlgorithmsComputational Complexity Of Graph AlgorithmsK-shortest PathsShortest Path In Directed GraphsShortest Path In Undirected GraphsShortest Path ProblemsShortest Paths
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.
2
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
E. N. Gilbert, H. O. Pollak · SIAM Journal on Applied Mathematics · 1968 · 938 citations