Quick links

Maintaining Bipartite Matchings in the Presence of Failures

Report ID:
September 1992
Download Formats:


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.
  • Follow us: Facebook Twitter Linkedin