Parallel Algorithms for Maximal Linear Forests

Ryuhei UEHARA  Zhi-Zhong CHEN  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A   No.4   pp.627-634
Publication Date: 1997/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
parallel algorithms,  randomized parallel algorithms,  graph algorithms,  linear forests,  maximal matchings,  maximal independent sets,  

Full Text: PDF>>
Buy this Article

The maximal linear forest problem is to find, given a graph G = (V, E), a maximal subset of V that induces a linear forest. Three parallel algorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n2 processors on a CRCW PRAM. The second one is deterministic and runs in O(log 2n) timeusing n4 processors on an EREW PRAM. The last one is deterministic and runs in O(log 5n) time using n3 processors on an EREW PRAM. The results put the problem in the class NC.