An efficient distributed algorithm for maximum matching in general graphs |
| |
| Authors: | Michael M Wu and Michael C Loui |
| |
| Affiliation: | (1) Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 61801 Urbana, IL, USA |
| |
| Abstract: | We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n
5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader.Work on this paper has been supported by the Office of Naval Research under Contract N00014-85-K-0570. |
| |
| Keywords: | Matching Distributed algorithms Graph algorithms Combinatorial optimization |
| 本文献已被 SpringerLink 等数据库收录！ |
