A generalized model for understanding evasiveness

DOI10.1016/0020-0190(89)90214-7MaRDI QIDQ1825645zbMATH OpenOpenAlexFDO

Authors Alok Aggarwal, Don Coppersmith, Daniel J. Kleitman

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90214-7

zbMATH Keywords

graph propertiesevasiveness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Searching for an edge in a graph
• A topological approach to evasiveness
• The smallest nonevasive graph property
• An asymptotic bound for the complexity of monotone graph properties
• Evasiveness of subgraph containment and related properties

Cites work

• On recognizing graph properties from adjacency matrices

Cited in

(9)

• Graph properties in node-query setting: effect of breaking symmetry
• scientific article; zbMATH DE number 3902707 (Why is no real title available?)
• Searching for an edge in a graph
• Reconstructing graphs from cut-set sizes
• Monotone Bipartite Graph Properties are Evasive
• scientific article; zbMATH DE number 4003527 (Why is no real title available?)
• The smallest nonevasive graph property
• Connectivity vs. reachability
• scientific article; zbMATH DE number 1688357 (Why is no real title available?)

This page was built for publication: A generalized model for understanding evasiveness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1825645)