An efficient distributed algorithm for maximum matching in general graphs |
| |
| Authors: | Michael M. Wu 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
