Analysis of an exhaustive search algorithm in random graphs and the n^{c\log n} -asymptotics

Cyril Banderier, Hsien-Kuei Hwang, Vlady Ravelomanana +1

We analyze the cost used by a naive exhaustive search algorithm for finding a maximum independent set in random graphs under the usual G_{n,p} -model where each possible edge appea…