Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2011-10-03
Computer Science
Distributed, Parallel, and Cluster Computing
1+15 pages
Scientific paper
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 algorithm that finds a maximal matching in $k-1$ synchronous communication rounds. The present work shows that the greedy algorithm is optimal in the general case: any algorithm that finds a maximal matching in anonymous, $k$-edge-coloured graphs requires $k-1$ rounds. If we focus on graphs of maximum degree $\Delta$, it is known that a maximal matching can be found in $O(\Delta + \log^* k)$ rounds, and prior work implies a lower bound of $\Omega(\polylog(\Delta) + \log^* k)$ rounds. Our work closes the gap between upper and lower bounds: the complexity is $\Theta(\Delta + \log^* k)$ rounds. To our knowledge, this is the first linear-in-$\Delta$ lower bound for the distributed complexity of a classical graph problem.
Hirvonen Juho
Suomela Jukka
No associations
LandOfFree
Distributed Maximal Matching: Greedy is Optimal does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Distributed Maximal Matching: Greedy is Optimal, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed Maximal Matching: Greedy is Optimal will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-271257