52 citations · 106 across the 21 of their papers we have counts for
5 papers · 1 filter
Optimal Distributed Covering Algorithms
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…
Optimal Distributed Weighted Set Cover Approximation
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank . This problem is equivalent to the Minimum…
A Deterministic Distributed -Approximation for Weighted Vertex Cover in Rounds
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi +1
We present a deterministic distributed -approximation algorithm for the Minimum Weight Vertex Cover problem in the CONGEST model whose round complexity is $O(\log n \log Δ/ \log…
Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model
Guy Even, Reut Levi, Moti Medina
In this paper we present distributed testing algorithms of graph properties in the CONGEST-model [Censor-Hillel et al. 2016]. We present one-sided error testing algorithms in the g…
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…