Distributed Maximal Matching: Greedy is Optimal

Juho Hirvonen, Jukka Suomela

We study distributed algorithms that find a maximal matching in an anonymous, edge-coloured graph. If the edges are properly coloured with $k$ colours, there is a trivial greedy al…