An efficient distributed algorithm for maximum matching in general graphs
| Autor: | Michael C. Loui, Michael M. Wu |
|---|---|
| Rok vydání: | 1990 |
| Předmět: |
Theoretical computer science
General Computer Science Matching (graph theory) Computer science Applied Mathematics Computer Science Applications Combinatorics Cardinality Distributed algorithm Theory of computation Bipartite graph Combinatorial optimization Blossom algorithm MathematicsofComputing_DISCRETEMATHEMATICS Hopcroft–Karp algorithm |
| Zdroj: | Algorithmica. 5:383-406 |
| ISSN: | 1432-0541 0178-4617 |
| DOI: | 10.1007/bf01840395 |
| Popis: | We present a distributed algorithm for maximum cardinality matching in general graphs. On a general graph withn vertices, our algorithm requiresO(n5/2) messages in the worst case. On trees, our algorithm computes a maximum matching usingO(n) messages after the election of a leader. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink