Finding a Maximum Independent Set in a Sparse Random Graph

DOI10.1137/060661090zbMath1167.05329OpenAlexW2020489728MaRDI QIDQ3629470

Eran Ofek

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

maximum independent setaverage case

Mathematics Subject Classification ID

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

Related Items (1)

On the independent set problem in random graphs

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