Back to Search
Start Over
A new self-stabilizing maximal matching algorithm
- Source :
-
Theoretical Computer Science . Mar2009, Vol. 410 Issue 14, p1336-1345. 10p. - Publication Year :
- 2009
-
Abstract
- Abstract: The maximal matching problem has received considerable attention in the self-stabilizing community. Previous work has given several self-stabilizing algorithms that solve the problem for both the adversarial and the fair distributed daemon, the sequential adversarial daemon, as well as the synchronous daemon. In the following we present a single self-stabilizing algorithm for this problem that unites all of these algorithms in that it has the same time complexity as the previous best algorithms for the sequential adversarial, the distributed fair, and the synchronous daemon. In addition, the algorithm improves the previous best time complexities for the distributed adversarial daemon from and to where is the number of processes, is the number of edges, and is the maximum degree in the graph. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 410
- Issue :
- 14
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 36781046
- Full Text :
- https://doi.org/10.1016/j.tcs.2008.12.022