For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Parallel Algorithms for Maximal Linear Forests
Ryuhei UEHARA Zhi-Zhong CHEN
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1997/04/25
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>>
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.