Distributed Half-Integral Matching and Beyond

Sameep Dahal, Jukka Suomela

By prior work, it is known that any distributed graph algorithm that finds a maximal matching requires $\Omega ({\log }^{\ast }n)$ communication rounds, while it is possible to find a maximal fr…