Improved Deterministic Distributed Maximum Weight Independent Set Approximation in Sparse Graphs

Yuval Gil

We design new deterministic CONGEST approximation algorithms for \emph{maximum weight independent set (MWIS)} in \emph{sparse graphs}. As our main results, we obtain new $\Delta (1+\epsilon )$-a…