Large independent sets in random regular graphs
We present algorithmic lower bounds on the size sd of the largest independent sets of vertices in random d-regular graphs, for each fixed d ≥ 3. For instance, for d = 3 we prove that, for graphs on n vertices, sd ≥ 0.43475 n with probability approachi
|Collections||ANU Research Publications|
|Source:||Theoretical Computer Science|
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.