Two distributed algorithms for finding matchings on a graph.

Abstract

Two new distributed algorithms for finding matchings on a graph are presented. The first algorithm generates a spanning matching. A spanning matching on a graph is one with respect to which no two adjacent nodes are both free. Starting from any matching, the second algorithm proceeds in phases until a maximum matching is found. In each phase, the algorithm finds at least one augmenting path on the graph with respect to the current matching and then augments the current matching. The algorithm terminates when no more augmenting paths can be found. The main features of our algorithms are the use of multiple virtual alternating trees for finding augmenting paths without using messages for synchronization, "shrinking blossoms" and the labelling. Both algorithms are based on asynchronous networks and assume that only local information is available in each process. Our first algorithm has worst-case communication complexity O(m) and time complexity O(n); and our second algorithm has worst-case communication complexity O(mn) and time complexity O(n$\sp2$), where n is the number of nodes and m is the number of edges of the graph.