20 citations · 82 across the 28 of their papers we have counts for
37 papers
Diameter-Free Distributed Frequency Control for Graph Coloring in the CONGEST Model
Amit Nir, David Peleg
This paper presents two randomized proper-coloring algorithms that control color frequencies in the synchronous CONGEST model without paying a diameter-dependent coordination cost.…
Recurrent Problems in the LOCAL model
Akanksha Agrawal, John Augustine, David Peleg +1
The paper considers the SUPPORTED model of distributed computing introduced by Schmid and Suomela [HotSDN'13], generalizing the LOCAL and CONGEST models. In this framework, multipl…
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…
The Power of Small Coalitions under Two-Tier Majority on Regular Graphs
Pavel Chebotarev, David Peleg
In this paper, we study the following problem. Consider a setting where a proposal is offered to the vertices of a given network , and the vertices must conduct a vote and decid…
Singularly Near Optimal Leader Election in Asynchronous Networks
Shay Kutten, William K. Moses, Gopal Pandurangan +1
This paper concerns designing distributed algorithms that are {\em singularly optimal}, i.e., algorithms that are {\em simultaneously} time and message {\em optimal}, for the funda…
Budgeted Dominating Sets in Uncertain Graphs
Keerti Choudhary, Avi Cohen, N. S. Narayanaswamy +2
We study the {\em Budgeted Dominating Set} (BDS) problem on uncertain graphs, namely, graphs with a probability distribution associated with the edges, such that an edge ex…