Maintaining Bipartite Matchings in the Presence of Failures
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
- Proc. of 7th Internat. Parallel Processing Symposium,
April 13-16, 1993, Newport Beach, California.
- Networks, 23(5),
pp. 459-471, August 1993.