Lower bounds on the complexity of graph properties
Valerie Jean King · 1988
In this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, …, n} has a given property by asking questions of the form “Is edge in the graph?”. The complexity of a property is the number of questions which must be asked in the worst case.