Back to Search
Start Over
A self-stabilizing -approximation algorithm for the maximum matching problem
- Source :
-
Theoretical Computer Science . Sep2011, Vol. 412 Issue 40, p5515-5526. 12p. - Publication Year :
- 2011
-
Abstract
- Abstract: The matching problem asks for a large set of disjoint edges in a graph. It is a problem that has received considerable attention in both the sequential and the self-stabilizing literature. Previous work has resulted in self-stabilizing algorithms for computing a maximal (-approximation) matching in a general graph, as well as computing a -approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a -approximation to the maximum matching problem in a general graph. We show that our new algorithm, when run under a distributed adversarial daemon, stabilizes after at most rounds. However, it might still use an exponential number of time steps. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 412
- Issue :
- 40
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 65046687
- Full Text :
- https://doi.org/10.1016/j.tcs.2011.05.019