Large independent sets in random regular graphs
Date
2009
Authors
Duckworth, William
Zito, Michele
Journal Title
Journal ISSN
Volume Title
Publisher
Elsevier
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.43475 n with probability approachi
Description
Keywords
Keywords: Independent set; Independent sets; Lower bounds; Random D-regular graphs; Random graphs; Random regular graph; Control theory; Graph theory; Set theory; Approximation algorithms Approximation algorithms; Independent sets; Random graphs
Citation
Collections
Source
Theoretical Computer Science
Type
Journal article