13 citations · 23 across the 12 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.DC2017
Adapting Local Sequential Algorithms to the Distributed Setting
Ken-ichi Kawarabayashi, Gregory Schwartzman
It is a well known fact that sequential algorithms which exhibit a strong "local" nature can be adapted to the distributed setting given a legal graph coloring. The running time of…
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 model which completes in $O(\texttt{MIS}(G)\cdot \l…
cs.DS2017★ 13 cited
A -Approximation for Maximum Weight Matching in the Semi-Streaming Model
Ami Paz, Gregory Schwartzman
We present a simple deterministic single-pass -approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently…