The critical complexity of graph properties
From MaRDI portal
Publication:795503
DOI10.1016/0020-0190(84)90019-XzbMath0542.68026OpenAlexW2089621728MaRDI QIDQ795503
Publication date: 1984
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(84)90019-x
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Threshold circuits of bounded depth, Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions, Alternation, sparsity and sensitivity: bounds and exponential gaps, Block sensitivity of weakly symmetric functions, On induced subgraphs of the cube, An improved lower bound on the sensitivity complexity of graph properties, Block sensitivity of minterm-transitive functions, Properties of complexity measures for PRAMs and WRAMs, A tighter relation between sensitivity complexity and certificate complexity, On the relationship between energy complexity and other Boolean function measures, Certificate complexity of elementary symmetric Boolean functions, Complexity measures and decision tree complexity: a survey.
Cites Work
