A parallel algorithm for the Steiner tree problem Conference

Makki, K, Been, K, Pissinou, N. (1993). A parallel algorithm for the Steiner tree problem . 380-384. 10.1109/ICCI.1993.315344

cited authors

  • Makki, K; Been, K; Pissinou, N



  • The Steiner problem in graphs is to find the minimum cost tree which spans at least a given subset of V, where V is the set of vertices in the graph. This problem has a wide variety of practical applications, including wire routing in physical VLSI design. Since the problem is NP-complete, much work has been devoted to developing approximate solutions such as the one proposed by V.J. Rayward-Smith (1988). In this paper, we identify the Rayward-Smith's algorithm as being appropriate for parallelization, and describe a parallel implementation of that algorithm. We also show that linear speedup is achievable on the PRAM model with the number of processors p ≤ |V|.

publication date

  • January 1, 1993

Digital Object Identifier (DOI)

International Standard Book Number (ISBN) 10

International Standard Book Number (ISBN) 13

start page

  • 380

end page

  • 384