MAINTAINING BIPARTITE MATCHINGS IN THE PRESENCE OF FAILURES

We present an on-line distributed reconfiguration algorithm for findin g a new maximum matching incrementally after some nodes have failed. O ur algorithm is deadlock-free and, with k failures, maintains at least M - k matching pairs during the reconfiguration process, where M is t he size of the original maximum matching. The algorithm tolerates fail ures that occur during reconfiguration. The worst-case reconfiguration time is O(k min(Absolute value of A, Absolute value of B)) after k fa ilures, where A and B are the node sets, but simulations show that the average-case reconfiguration time is much better. The algorithm is al so simple enough to be implemented in hardware. (C) 1993 by John Wiley & Sons, Inc.