Very large cliques are easy to detect

DOI10.1016/J.DISC.2007.07.036zbMath1159.05318OpenAlexW1983846889MaRDI QIDQ932700

Stasys P. Jukna, Alexander E. Andreev

Publication date: 11 July 2008

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/609/

zbMATH Keywords

monotone circuitscritical graphsvertex coverclique functionperfect hashing

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The monotone circuit complexity of Boolean functions
• Induced subsets
• On the incompressibility of monotone DNFs
• On the Asymptotic Complexity of Matrix Multiplication
• A Problem in Graph Theory
• A Theorem on k-Saturated Graphs
• Explicit constructions of perfect hash families from algebraic curves over finite fields

This page was built for publication: Very large cliques are easy to detect