Journal
DISTRIBUTED COMPUTING
Volume 30, Issue 5, Pages 325-338Publisher
SPRINGER
DOI: 10.1007/s00446-015-0245-8
Keywords
Local distributed algorithms; Lower bounds; Maximal edge packing; Maximal fractional matching
Categories
Funding
- Academy of Finland [132380, 252018]
- University of Helsinki
- Academy of Finland (AKA) [252018, 132380, 252018, 132380] Funding Source: Academy of Finland (AKA)
Ask authors/readers for more resources
By prior work, there is a distributed graph algorithm that finds a maximal fractional matching (maximal edge packing) in O(Delta) rounds, independently of n; here Delta is the maximum degree of the graph and n is the number of nodes in the graph. We show that this is optimal: there is no distributed algorithm that finds a maximal fractional matching in o(Delta) rounds, independently of n. Our work gives the first linear-in-Delta lower bound for a natural graph problem in the standard model of distributed computing-prior lower bounds for a wide range of graph problems have been at best logarithmic in Delta.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available