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

DOI10.1007/BFB0030876MaRDI QIDQ6085752zbMATH OpenFDO

Authors Marcus Peinado

Publication date 12 December 2023

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 753972
• Hard graphs for randomized subgraph exclusion algorithms
• scientific article; zbMATH DE number 1182770
• scientific article; zbMATH DE number 956847
• Derandomized graph products

Cites work

• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 753972 (Why is no real title available?)
• 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

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