
We give a deterministic distributed approximation algorithm for the maximum matching problem in graphs of bounded arboricity. Specifically, given 0 < ?< 1 and a positive integer a, the algorithm finds a matching of size at least (1 ? ?)m(G), where m(G) is the size of the maximum matching in an n-vertex graph G with arboricity at most a. The algorithm runs in O(log* n) rounds in the message passing model and it is the first sublogarithmic algorithm for the problem on such a wide class of graphs. Moreover, the result implies that the known $\Omega(\sqrt{\log n/\log\log n})$ lower bound on the time complexity for a constant or polylogarithmic approximation does not hold for graphs of bounded arboricity.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
