Distributed algorithm for approximating the maximum matching (Q1887042)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Distributed algorithm for approximating the maximum matching |
scientific article; zbMATH DE number 2118326
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Distributed algorithm for approximating the maximum matching |
scientific article; zbMATH DE number 2118326 |
Statements
Distributed algorithm for approximating the maximum matching (English)
0 references
23 November 2004
0 references
The authors present an \(O(\log^6 n)\)-time distributed algorithm computing a matching of size at least \(\frac{2}{3}| M^*| \) where \(M^*\) is a maximum matching and \(n\) is the number of vertices of the input graph. The approximation factor \(2/3\) relies on a theorem due to \textit{T. Fischer, A. V. Goldberg, D. J. Haglin} and \textit{S. Plotkin} [``Approximating matchings in parallel'', Inf. Process. Lett. 46, 115--118 (1993; Zbl 0784.68065)].
0 references
distributed algorithm
0 references
maximum matching
0 references
