Name
Abstract | ||
|---|---|---|
The authors present an on-line distributed reconfiguration algorithm for finding a new maximum matching incrementally after some nodes have failed. Their 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( mod A mod , mod B mod )) 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. |
Year | DOI | Venue |
|---|---|---|
1993 | 10.1109/IPPS.1993.262856 | Newport, CA |
Keywords | Field | DocType |
m-k matching pair,reconfiguration algorithm,k min,original maximum matching,k failure,average-case reconfiguration time,bipartite matchings,mod b mod,worst-case reconfiguration time,algorithm tolerates failure,reconfiguration process,distributed algorithms,maximum matching,computer science,bipartite matching,fault tolerance,very large scale integration,bipartite graph | Deadlock free,Mod,Computer science,Bipartite graph,Parallel computing,Matching (graph theory),Distributed algorithm,Control reconfiguration,Reconfiguration algorithm,Distributed computing | Journal |
Volume | Issue | ISSN |
23 | 5 | 0028-3045 |
ISBN | Citations | PageRank |
0-8186-3442-1 | 2 | 0.42 |
References | Authors | |
6 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edwin Hsing-mean Sha | 1 | 2 | 0.42 |
| Kenneth Steiglitz | 2 | 1128 | 660.13 |