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. © 1993 by John Wiley & Sons, Inc.