28 citations · 42 across the 10 of their papers we have counts for
3 papers · 1 filter
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm
Fabien Dufoulon, Shay Kutten, William K. Moses +2
A singularly (near) optimal distributed algorithm is one that is (near) optimal in \emph{two} criteria, namely, its time and message complexities. For \emph{synchronous} CONGEST ne…
Awake Complexity of Distributed Minimum Spanning Tree
John Augustine, William K. Moses, Gopal Pandurangan
We study the distributed minimum spanning tree (MST) problem, a fundamental problem in distributed computing. It is well-known that distributed MST can be solved in $\tilde{O}(D+\s…
Distributed MIS in Awake Complexity
Fabien Dufoulon, William K. Moses, Gopal Pandurangan
Maximal Independent Set (MIS) is one of the fundamental and most well-studied problems in distributed graph algorithms. Even after four decades of intensive research, the best-know…