Cohen, Johanne
[Verfasser:in];
Maâmra, Khaled
[Verfasser:in];
Manoussakis, George
[Verfasser:in];
Pilard, Laurence
[Verfasser:in]
;
Johanne Cohen and Khaled Maâmra and George Manoussakis and Laurence Pilard
[Mitwirkende:r]
Polynomial Self-Stabilizing Maximum Matching Algorithm with Approximation Ratio 2/3
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
We present the first polynomial self-stabilizing algorithm for finding a (2/3)-approximation of a maximum matching in a general graph. The previous best known algorithm has been presented by Manne et al. and has a sub-exponential time complexity under the distributed adversarial daemon. Our new algorithm is an adaptation of the Manne et al. algorithm and works under the same daemon, but with a time complexity in O(n^3) moves. Moreover, our algorithm only needs one more boolean variable than the previous one, thus as in the Manne et al. algorithm, it only requires a constant amount of memory space (three identifiers and two booleans per node).