Finding a Maximum Independent Set in a Sparse Random Graph

DOI10.1137/060661090MaRDI QIDQ3629470zbMATH OpenOpenAlexFDO

Authors Eran Ofek, Uriel Feige

Publication date 27 May 2009

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/0b197d6ba627f7c2acd2ce886e1eeef1210714c5

zbMATH Keywords

average casemaximum independent set

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Finding Large Independent Sets in Polynomial Expected Time
• Independent sets in random sparse graphs
• On the independent set problem in random graphs
• scientific article; zbMATH DE number 1962840

Cited in

(11)

• Optimal low-degree hardness of maximum independent set
• On the independent set problem in random graphs
• All maximal independent sets and dynamic dominance for sparse graphs
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method
• Finding Large Independent Sets in Polynomial Expected Time
• Independent sets in random sparse graphs
• scientific article; zbMATH DE number 1962840 (Why is no real title available?)
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• How to hide a clique?
• How to hide a clique?
• On finding randomly planted cliques in arbitrary graphs

This page was built for publication: Finding a Maximum Independent Set in a Sparse Random Graph

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