The Manne et al. self-stabilizing 2/3-approximation matching algorithm is sub-exponential
classification
💻 cs.DC
keywords
matchingalgorithmapproximationmannesub-exponentialcomplexitycomputingdesigned
read the original abstract
Manne et al. designed the first algorithm computing a maximal matching that is a 2/3 -approximation of the maximum matching in $O(^2n)$ moves. However, the complexity tightness was not proved. In this paper, we exhibit a sub-exponential execution of this matching algorithm.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.