Large independent sets in random regular graphs

DOI10.1016/j.tcs.2009.08.025zbMath1194.68169OpenAlexW2082345630MaRDI QIDQ1034530

Michele Zito, William Duckworth

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.025

zbMATH Keywords

random graphsindependent setsapproximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items

Properties of regular graphs with large girth via local algorithms, The cook-book approach to the differential equation method, Subgroup growth of right‐angled Artin and Coxeter groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 3-star factors in random \(d\)-regular graphs
• On the independence number of random graphs
• On the independence and chromatic numbers of random regular graphs
• On approximation properties of the independent set problem for low degree graphs
• Analysis of greedy algorithms on graphs with bounded degrees
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Differential equations for random processes and random graphs
• Approximation Algorithms for Independent Sets in Map Graphs
• Cliques in random graphs
• Approximation algorithms for NP-complete problems on planar graphs
• On the independence number of random cubic graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Combinatorial Geometry and Graph Theory
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph