Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE

DOI10.1007/bfb0030876zbMath1527.68167MaRDI QIDQ6085752

Marcus Peinado

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• A guided tour of Chernoff bounds
• Approximating maximum independent sets by excluding subgraphs
• Large Cliques Elude the Metropolis Process

This page was built for publication: Improved lower bounds for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE