Evasiveness of Graph Properties and Topological Fixed-Point Theorems

Carl A. Miller

Many graph properties (e.g., connectedness, containing a complete subgraph) are known to be difficult to check. In a decision-tree model, the cost of an algorithm is measured by th…