Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model

N. Bourgeois, R. Catellier, T. Denat +1

We study average-case complexity of branch-and-bound for maximum independent set in random graphs under the $\mathcal{G}(n,p)$ distribution. In this model every pair $(u,v)$ of ver…