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

DOI10.1007/BFB0030876zbMATH Open1527.68167MaRDI QIDQ6085752FDOQ6085752

Authors: Marcus Peinado 

Publication date: 12 December 2023

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

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

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)

Cites Work

• Title not available (Why is that?)
• A guided tour of Chernoff bounds
• Large Cliques Elude the Metropolis Process
• Approximating maximum independent sets by excluding subgraphs
• Title not available (Why is that?)

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)