Asymptotic performance of the Grimmett-McDiarmid heuristic

arXiv1912.04772MaRDI QIDQ6330840FDOQ6330840

Authors: Yuval Filmus 

Publication date: 10 December 2019

Abstract: Grimmett and McDiarmid suggested a simple heuristic for finding stable sets in random graphs. They showed that the heuristic finds a stable set of size $simlo{g}_{2}n$ (with high probability) on a $G(n,1/2)$ random graph. We determine the asymptotic distribution of the size of the stable set found by the algorithm.

This page was built for publication: Asymptotic performance of the Grimmett-McDiarmid heuristic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6330840)