Sequential Algorithms and Independent Sets Discovering on Large Sparse Random Graphs

Paola Bermolen, Matthieu Jonckheere, Federico Larroca +1

Computing the size of maximum independent sets is a NP-hard problem for fixed graphs. Characterizing and designing efficient algorithms to estimate this independence number for ran…