Decision Tree Complexity of Graph Properties with Dimension at Most 5

• 作 者: 高随祥 林国辉
• 机 构: Mathematics Department, Graduate School, University of Science and Technology of China Beijing 10003
• 出 处: Journal of Computer Science and Technology
• 发表日期: 2000年05期
• 关键词: monotone graph property decision tree complexity elusive

A graph property is a set of graphs such that if the set contains some graph G then it also contains each isomorphic copy of G (with the same vertex set). A graph property P on n ventices is said to be elusive, if every decision tree algorithm recogniz