Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs
Sukumar Mondal, Madhumangal Pal, Tapan Kumar Pal · International Journal of Computer Mathematics · 2003
This paper presents an optimal sequential and an optimal parallel algorithm to compute a minimum cardinality Steiner set and a Steiner tree. The sequential algorithm takes O ( n ) time and parallel algorithm takes O (log n ) time and O ( n /log n ) processors on an EREW PRAM model.