Distributed Approximation of Maximum Independent Set and Maximum Matching

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

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