zbMATH — the first resource for mathematics

Maintaining bipartite matchings in the presence of failures. (English) Zbl 0794.90020
Summary: 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.
90B25 Reliability, availability, maintenance, inspection in operations research
90B15 Stochastic network models in operations research
Full Text: DOI
[1] Awerbuch, J. Assoc. Comput. Math. 32 pp 804– (1985) · Zbl 0628.68045 · doi:10.1145/4221.4227
[2] Greene, J. Assoc. Comp. Mach. 31 pp 694– (1984) · Zbl 0632.94033 · doi:10.1145/1634.2377
[3] Hopocroft, SIAM J. Comput. 2 pp 225– (1973)
[4] , and , An optimal algorithm for on-line bipartite matching. Proceedings of the 22th Annual ACM Symposium Theory of Computing (1990) 352–358.
[5] and , Spare allocation and reconfiguration in large area VLSI. Proceedings of 25th ACM/IEEE Design Automation Conference (1988) 609–612.
[6] and , An O(|V| |E|) algorithm for finding maximum matching in general graphs. Proceedings of the Foundations of Computer Science (1980) 17–27.
[7] and , Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs, N.J. (1981).
[8] and , Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: Maximum matchings. Proceedings of the 5th Annual ACM Symposium on Principles of Distributed Computing (1986) 282–292.
[9] Sha, IEEE Trans. Comput.
[10] and , Explicit constructions for reliable reconfigurable array architectures. Proceedings of the Third IEEE Symposium Parallel and Distributed Processing, Dallas, Texas, (Dec. 1991) 640–647.
[11] Wu, Algorithmica 5 pp 383– (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.