A parallel algorithm to generate all maximal independent sets on permutation graphs
Madhumangal Pal · International Journal of Computer Mathematics · 1998
In this paper, an time and processors parallel algorithm is designed to generate all paths from leaf nodes to the root of a tree, where n' is the total number of such paths. Using this algorithm an time and processors parallel algorithm is designed to generate all maximal independent sets on permutation graphs, where n represents the number of vertices(nodes) N is the output size. Both the algorithms run on an EREW PRAM.