PARALLEL ALGORITHMS FOR MAXIMAL LINEAR FORESTS

Authors
UEHARA R CHEN ZZ
Citation
R. Uehara et Zz. Chen, PARALLEL ALGORITHMS FOR MAXIMAL LINEAR FORESTS, IEICE transactions on fundamentals of electronics, communications and computer science, E80A(4), 1997, pp. 627-634
Citations number
20
Categorie Soggetti
Engineering, Eletrical & Electronic","Computer Science Hardware & Architecture","Computer Science Information Systems
Journal title
IEICE transactions on fundamentals of electronics, communications and computer science → ACNP
ISSN journal
09168508
Volume
E80A
Issue
4
Year of publication
1997
Pages
627 - 634
Database
ISI
SICI code
0916-8508(1997)E80A:4<627:PAFMLF>2.0.ZU;2-9
Abstract
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 a lgorithms for this problem are presented. The first one is randomized and runs in O(log n) expected time using n(2) processors on a CRCW PRA M. The second one is deterministic and runs in O(log(2) n) time using n(4) processors on an EREW PRAM. The last one is deterministic and run s in O(log(5) n) time using n(3) processors on an EREW PRAM. The resul ts put the problem in the class NC.