Using maximal independent sets to solve problems in parallel

By using an O((log n)2) time EREW PRAM algorithm for a maximal independent set problem (MIS), we show the following two results: (1) Given a graph, the maximal vertex-induced subgraph satisfying a hereditary graph property π can be found in time 0(Δλ(π)Tπ(n)(log n)2) using a polynomial number of processors, where λ(π) is the maximum of diameters of minimal graphs violating π and Tπ(n) is the time needed to decide whether a graph with n vertices satisfies π. (2) Given a family C = c1,...,c m of subsets of a finite set S = 1,..., n with S = (U i=1 m ci, a minimal set cover for S can be computed on an EREW PRAM in time O(αΒ(log(n + m))2) using a polynomial number of processors, where α=max{¦ci,¦ ¦i=1,..., m and Β = max{¦dj¦ ¦j = 1,..., n.