Improved Distributed Approximations for Maximum Independent Set

Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1

We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let $n$ and…