Large independent sets in random regular graphs |
| |
Authors: | William Duckworth Michele Zito |
| |
Affiliation: | 1. Mathematical Sciences Institute, Australian National University, Canberra, ACT 0200, Australia;2. Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom |
| |
Abstract: | 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.43475n with probability approaching one as n tends to infinity. |
| |
Keywords: | Random graphs Independent sets Approximation algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|