Stabilizing maximum matching in bipartite networks

摘要

A matching E^sub [M-script]^ of graph G = (V, E) is a subset of the edges E, such that no vertex in V is incident to more than one edge in E^sub [M-script]^. The matching E^sub [M-script]^ is maximum if there is no matching in G with size strictly larger than the size of E^sub [M-script]^. In this paper, we present a distributed stabilizing algorithm for finding maximum matching in bipartite graphs based on the stabilizing PIF algorithm of Cournier et al. (Proceedings of 21st IEEE international conference on distributed computing systems, 91-98, 2001). Since our algorithm is stabilizing, it does not require initialization and withstands transient faults. The complexity of the proposed algorithm is O(d × n) rounds, where d is the diameter of the communication network and n is the number of nodes in the network. The space complexity is O(log Δ + log d), where Δ is the largest degree of all the nodes in the communication network. In addition, an optimal version of the proposed algorithm finding maximum matching in linear time is also presented.