Finding Large Independent Sets in Polynomial Expected Time

DOI10.1017/S0963548306007553MaRDI QIDQ3412105zbMATH OpenOpenAlexFDO

Authors Amin Coja-Oghlan

Publication date 5 December 2006

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548306007553

zbMATH Keywords

random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1962840
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Finding a Maximum Independent Set in a Sparse Random Graph
• Heuristics for semirandom graph problems
• scientific article; zbMATH DE number 1929938

Cited in

(12)

• Heuristics for semirandom graph problems
• Faster exponential-time algorithms for approximately counting independent sets
• Approximating independent set in perturbed graphs
• The resolution complexity of independent sets and vertex covers in random graphs
• On the independent set problem in random graphs
• Exponential Time Complexity of Weighted Counting of Independent Sets
• Finding a Maximum Independent Set in a Sparse Random Graph
• scientific article; zbMATH DE number 1962840 (Why is no real title available?)
• Introduction to Semirandom Models
• Constructing concrete hard instances of the maximum independent set problem
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On finding randomly planted cliques in arbitrary graphs

This page was built for publication: Finding Large Independent Sets in Polynomial Expected Time

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