Evasiveness of Subgraph Containment and Related Properties

DOI10.1137/S0097539700382005zbMath1051.68071WikidataQ56701654 ScholiaQ56701654MaRDI QIDQ2784484

Yaoyun Shi, Amit Chakrabarti, Subhash A. Khot

Publication date: 23 April 2002

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

evasiveness; topological method; decision tree complexity; monotone graph properties; graph property testing

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

An asymptotic bound for the complexity of monotone graph properties