Maintaining Bipartite Matchings in the Presence of Failures

Abstract:

We present an on-line distributed reconfiguration algorithm for
finding a new maximum matching incrementally after some nodes have
failed. Our algorithm is deadlock free, and with k failures
maintains at least M - k matching pairs during the reconfiguration
process, where M is the size of the original maximum matching. The
algorithm tolerates failures that occur during reconfiguration. The
worst-case reconfiguration time is
O(k min(|A|, |B|)) after k
failures, where A and B are the node sets, but simulations show
that the average-case reconfiguration time is much better. The
algorithm is also simple enough to be implemented in hardware.

This technical report has been published as

Maintaining Bipartite Matchings in the Presence of
Failures. Edwin Hsing-Mean Sha and Kenneth
Steiglitz,

Proc. of 7th Internat. Parallel Processing Symposium,
April 13-16, 1993, Newport Beach, California.

Networks, 23(5),
pp. 459-471, August 1993.