Parallel algorithms for f-matchings

Abstract In this chapter we present randomized and deterministic NC-algorithms for maximum and (inclusion) maximal f-matchings (which are natural generalizations of matchings). In particular each (usual) matching is a I-matching. Let G be an undirected graph with an integer capacity f(v) associated with each vertex v. A subset M of the set of edges of G is an f-matching if and only if each vertex v in G is incident to at most f(v) edges in M. An f-matching is maximal if and only if it is not properly contained in another f-matching. An example of a maximal f-matching containing 10 edges is illustrated in Figure 11.1; the maximum cardinality f-matching in this case has 11 edges. The parallel computation of a maximal f-matching is generally more difficult than that of a maximal matching. Obviously, a maximal f-matching can be computed in linear time by a greedy sequential algorithm. Unfortunately we do not know how to parallelize this algorithm. In Chapter 7 we presented an RNC¬ algorithm for maximal matchings. By generalizing this randomized algorithm we can present a simple randomized algorithm for maximal f-matching which runs in O(log3 n) time with O(n + m) processors. The deterministic NC-algorithm is much more complicated. It is based on the Israeli and Shiloach deterministic algorithm for maximal matchings, see [IS86]. It was generalized in [DGL93] to maximal f-matching.