Optimal Sequential And Parallel Algorithms To Compute A Steiner Tree On Permutation Graphs

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.

Keywords:

• Parallel Algorithms
• Analysis Of Algorithms
• Steiner Set
• Steiner Tree
• Permutation Graphs