25 citations · 49 across the 16 of their papers we have counts for
4 papers · 1 filter
Distributed Maximum Matching in Bounded Degree Graphs
Guy Even, Moti Medina, Dana Ron
We present deterministic distributed algorithms for computing approximate maximum cardinality matchings and approximate maximum weight matchings. Our algorithm for the unweighted c…
The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling
Dana Ron, Gilad Tsur
We study a basic problem of approximating the size of an unknown set in a known universe . We consider two versions of the problem. In both versions the algorithm can specif…
Best of Two Local Models: Local Centralized and Local Distributed Algorithms
Guy Even, Moti Medina, Dana Ron
We consider two models of computation: centralized local algorithms and local distributed algorithms. Algorithms in one model are adapted to the other model to obtain improved algo…
Local Algorithms for Sparse Spanning Graphs
Reut Levi, Dana Ron, Ronitt Rubinfeld
Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxa…