Maintaining Bipartite Matchings in the Presence of Failures
Report ID: TR-398-92Author: Steiglitz, Kenneth / Sha, Edwin Hsing-Mean
Date: 1992-10-00
Pages: 16
Download Formats: |Postscript|
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.