Evasiveness of Subgraph Containment and Related Properties
From MaRDI portal
Publication:2784484
DOI10.1137/S0097539700382005zbMath1051.68071WikidataQ56701654 ScholiaQ56701654MaRDI QIDQ2784484
Amit Chakrabarti, Subhash A. Khot, Yaoyun Shi
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
evasiveness; topological method; decision tree complexity; monotone graph properties; graph property testing
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, Counting induced subgraphs: a topological approach to \#W[1-hardness], Any monotone property of 3-uniform hypergraphs is weakly evasive