Treffer: Maintaining bipartite matchings in the presence of failures
Title:
Maintaining bipartite matchings in the presence of failures
Authors:
Source:
[1993] Proceedings Seventh International Parallel Processing Symposium. :57-64
Publisher Information:
IEEE Comput. Soc. Press, 1993.
Publication Year:
1993
Subject Terms:
on-line distributed reconfiguration algorithm, Stochastic network models in operations research, maximum matching, 03 medical and health sciences, 0302 clinical medicine, Reliability, availability, maintenance, inspection in operations research, 0102 computer and information sciences, 01 natural sciences
Document Type:
Fachzeitschrift
Article
File Description:
application/xml
DOI:
10.1109/ipps.1993.262856
DOI:
10.1002/net.3230230503
Access URL:
http://www.cs.princeton.edu/~ken/maintaining_matchings93.pdf
https://www.cs.princeton.edu/~ken/maintaining_matchings93.pdf
https://dblp.uni-trier.de/db/conf/ipps/ipps1993.html#ShaS93
http://ieeexplore.ieee.org/document/262856/
https://doi.org/10.1109/IPPS.1993.262856
https://dblp.uni-trier.de/db/journals/networks/networks23.html#ShaS93
https://core.ac.uk/display/21761070
https://www.cs.princeton.edu/~ken/maintaining_matchings93.pdf
https://dblp.uni-trier.de/db/conf/ipps/ipps1993.html#ShaS93
http://ieeexplore.ieee.org/document/262856/
https://doi.org/10.1109/IPPS.1993.262856
https://dblp.uni-trier.de/db/journals/networks/networks23.html#ShaS93
https://core.ac.uk/display/21761070
Rights:
Wiley Online Library User Agreement
Accession Number:
edsair.doi.dedup.....bfe8c0d6fb4de1e517953680c014781a
Database:
OpenAIRE
Weitere Informationen
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, withkfailures, maintains at leastM–kmatching pairs during the reconfiguration process, whereMis the size of the original maximum matching. The algorithm tolerates failures that occur during reconfiguration. The worst‐case reconfiguration time isO(kmin(|A|, |B|)) afterkfailures, whereAandBare 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.