PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
Krzysztof Diks, Oscar Garrido, Andrzej Lingas · International Journal of Foundations of Computer Science · 1993
Let k be a positive integer, a subset Q of the set of vertices of a graph G is k-dependent in G if each vertex of Q has no more than k neighbours in Q. We present a parallel algorithm which computes a maximal k-dependent set in a graph on n nodes in time O( log 4 n) on an EREW PRAM with O(n2) processors. In this way, we establish the membership of the problem of constructing a maximal k-dependent set in the class NC. Our algorithm can be easily adapted to compute a maximal k-dependent set in a graph of bounded valence in time O( log * n) using only O(n) EREW PRAM processors. Let f be a positive integer function defined on the set V of vertices of a graph G. A subset F of the set of edges of G is said to be an f-matching if every vertex vɛV is adjacent to at most f(v) edges in-F. We present the first NC algorithm for constructing a maximal f-matching. For a graph on n nodes and m edges the algorithm runs in time O( log 4 n) and uses O(n+m) EREW PRAM processors. For graphs of constantly bounded valence, we can construct a maximal f-matching in O( log * n) time on an EREW PRAM with O(n) processors.