Large independent sets on random $d$-regular graphs with fixed degree $d$

Raffaele Marino, Scott Kirkpatrick

This paper presents a linear prioritized local algorithm that computes large independent sets on a random $d$-regular graph with small and fixed degree $d$. We studied experimental…