Article ID Journal Published Year Pages File Type
10333929 Theoretical Computer Science 2011 12 Pages PDF
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 (12-approximation) matching in a general graph, as well as computing a 23-approximation on more specific graph types. In this paper, we present the first self-stabilizing algorithm for finding a 23-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 O(n2) rounds. However, it might still use an exponential number of time steps.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,