Name
Abstract | ||
|---|---|---|
A graph property is a set of graphs such that if the set contains some graphG then it also contains each isomorphic copy ofG (with the same vertex set). A graph propertyP onn vertices is said to be elusive, if every decision tree algorithm recognizingP must examine alln(n−1)/2, pairs of vertices in the worst case. Karp conjectured that every nontrivial monotone graph property is elusive. In this paper, this conjecture is proved for some cases. Especially, it is shown that if the abstract simplicial complex of a nontrivial monotone graph propertyP has dimension not exceeding 5, thenP is elusive. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/BF02950404 | J. Comput. Sci. Technol. |
Keywords | Field | DocType |
decision tree,simplicial complex | Mathematical optimization,Combinatorics,Graph power,Graph property,Computer science,Cubic graph,Cycle graph,Regular graph,Null graph,Butterfly graph,Complement graph,Distributed computing | Journal |
Volume | Issue | ISSN |
15 | 5 | 1860-4749 |
Citations | PageRank | References |
1 | 0.37 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suixiang Gao | 1 | 44 | 12.48 |
| Guohui Lin | 2 | 1301 | 107.34 |