Premium
Maintaining bipartite matchings in the presence of failures
Author(s) -
Sha Edwin HsingMean,
Steiglitz Kenneth
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230503
Subject(s) - control reconfiguration , bipartite graph , matching (statistics) , computer science , node (physics) , algorithm , simple (philosophy) , deadlock , line (geometry) , distributed computing , mathematics , theoretical computer science , graph , embedded system , engineering , statistics , philosophy , geometry , structural engineering , epistemology
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. © 1993 by John Wiley & Sons, Inc.