R. Bar-Yehuda

activity

20112020

most citedRandomized Algorithms for the Loop Cutset Problem

82 citations · 102 across the 4 of their papers we have counts for

collaborators

Showing cs.DCShow all

2 papers · 1 filter

cs.DC2017★ 4 cited

Distributed Approximation of Maximum Independent Set and Maximum Matching

Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari +1

We present a simple distributed $Δ$ -approximation algorithm for maximum weight independent set (MaxIS) in the $CONGEST$ model which completes in $O(\texttt{MIS}(G)\cdot \l…

cs.DC2016

A Distributed $(2 + ε)$ -Approximation for Vertex Cover in $O (lo g Δ/ ε lo g lo g Δ)$ Rounds

Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman

We present a simple deterministic distributed $(2 + ε)$ -approximation algorithm for minimum weight vertex cover, which completes in $O (lo g Δ/ ε lo g lo g Δ)$ rounds, where $Δ$ is the max…

Distributed Approximation of Maximum Independent Set and Maximum Matching

A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ/εloglogΔ) Rounds

A Distributed $(2 + ε)$ -Approximation for Vertex Cover in $O (lo g Δ/ ε lo g lo g Δ)$ Rounds