Large independent sets in random regular graphs

DOI10.1016/J.TCS.2009.08.025zbMATH Open1194.68169OpenAlexW2082345630MaRDI QIDQ1034530FDOQ1034530

Michele Zito, W. 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

approximation algorithmsrandom graphsindependent sets

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Connected graphs with a large number of independent sets
• Randomized greedy algorithm for independent sets in regular uniform hypergraphs with large girth
• 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
• Improved replica bounds for the independence ratio of random regular graphs
• Greedy maximal independent sets via local limits
• Fourier analysis and large independent sets in powers of complete graphs
• Large independent sets in regular graphs of large girth

This page was built for publication: Large independent sets in random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034530)