Very large cliques are easy to detect
type: Item
instance of: scholarly article
title: Very large cliques are easy to detect
zbMATH Open document ID: 1159.05318
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/609/
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5300690
zbMATH Keywords: clique function
zbMATH Keywords: monotone circuits
zbMATH Keywords: perfect hashing
zbMATH Keywords: vertex cover
zbMATH Keywords: critical graphs
author: Alexander E. Andreev
author: Stasys Jukna
MaRDI profile type: Publication
OpenAlex ID: W1983846889
cites work: The monotone circuit complexity of Boolean functions
cites work: Induced subsets
cites work: On the Asymptotic Complexity of Matrix Multiplication
cites work: A Problem in Graph Theory
cites work: A Theorem on k-Saturated Graphs
cites work: On the incompressibility of monotone DNFs
cites work: Q3688439
cites work: Q3758729
cites work: Explicit constructions of perfect hash families from algebraic curves over finite fields
cites work: Q3762226
DOI: 10.1016/J.DISC.2007.07.036
Recommended article: Detecting strong cliques
Recommended article: Large cliques and independent sets all over the place
Recommended article: Many cliques with few edges
Recommended article: Finding Large Clique Minors is Hard
Recommended article: Large clique is hard on average for resolution
Recommended article: Detecting cliques in CONGEST networks
Recommended article: Q5090906
Recommended article: On identifying dominant cliques.
Recommended article: Q5092335
description: scientific article; zbMATH DE number 5300690