Large independent sets in random regular graphs
Authors:
- William DuckworthWDWilliam Duckworth
- Michele ZitoMZMichele Zito
- 1 November 2009
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 410 (50) , 5236-5243
Abstract
No abstract availableKeywords
This publication has 14 references indexed in Scilit:
- 3-star factors in random d-regular graphsEuropean Journal of Combinatorics, 2006
- Approximation Algorithms for Independent Sets in Map GraphsJournal of Algorithms, 2001
- On Approximation Properties of the Independent Set Problem for Low Degree GraphsTheory of Computing Systems, 1999
- Algorithmic theory of random graphsRandom Structures & Algorithms, 1997
- On the independence number of random cubic graphsRandom Structures & Algorithms, 1994
- Approximation algorithms for NP-complete problems on planar graphsJournal of the ACM, 1994
- On the independence and chromatic numbers of random regular graphsJournal of Combinatorial Theory, Series B, 1992
- On the independence number of random graphsDiscrete Mathematics, 1990
- Cliques in random graphsMathematical Proceedings of the Cambridge Philosophical Society, 1976
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972