We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 15 Issue 5
September  2000
Turn off MathJax
Article Contents
Abstract
References
Related Articles
GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most5[J]. Journal of Computer Science and Technology, 2000, 15(5): 416-422.
Citation: GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most5[J]. Journal of Computer Science and Technology, 2000, 15(5): 416-422.
shu

Decision Tree Complexity of Graph Properties with Dimension at Most5

  • Mathematics Department; Graduate School; University of Science and Technology of China Beijing 100059; P.R. China Department of Computer Science; University of Waterloo; Waterloo; Canada;

More Information
  • Published Date: September 09, 2000
    Abstract
  • 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 recognizing P must examine all n(n - 1)/2 pairs of ventices 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 co…
    • FullText(HTML)
    • References (3)
  • [1]
    Rosenberg A L. On the time required to recognize properties of graphs: A problem. SIGACT News, 1973, 5(1): 15-16.
    [2]
    Kahn J, Saks M, Strutevant D. A topological approach to evasiveness. Combinatorica, 1984, 4(2): 297-306.
    [3]
    Bollobas B. Complete subgraphs are elusive. J. Cormbinatorial Theory (Ser.B), 1976, 21(2): 1-7. ……….
    • Relative Articles

  • Related Articles

    [1]Dao-Yun Xu, Zhi-Hong Tao. Complexities of Homomorphism and Isomorphism for Definite Logic Programs[J]. Journal of Computer Science and Technology, 2005, 20(6): 758-762.
    [2]Jin-Yi Cai, Hong Zhu. Progress in Computational Complexity Theory[J]. Journal of Computer Science and Technology, 2005, 20(6): 735-750.
    [3]LIU Tian. Some Structural Properties of SAT[J]. Journal of Computer Science and Technology, 2000, 15(5): 439-444.
    [4]JIANG Tao, LI Ming, Paul M.B. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5): 402-408.
    [5]GAO Suixiang, LIN Guohui. Decision Tree Complexity of Graph Properties with Dimension at Most 5[J]. Journal of Computer Science and Technology, 2000, 15(5).
    [6]JIANG Tao, LI Ming, Paul M.B.Vitanyi. Average-Case Analysis of Algorithms Using Kolmogorov Complexity[J]. Journal of Computer Science and Technology, 2000, 15(5).
    [7]MA Jun, YANG Bo, MA Shaohan. A Practical Algorithm for the Minimum Rectilinear Steiner Tree[J]. Journal of Computer Science and Technology, 2000, 15(1): 96-99.
    [8]GAO Xiaoshan, ZHU Changcai. Automated Generation of Kempe Linkageand Its Complexity[J]. Journal of Computer Science and Technology, 1999, 14(5): 460-467.
    [9]Zhang Bo, Zhang Ling. The Complexity of Recognition in the Single-Layered PLN Network with Feedback Connections[J]. Journal of Computer Science and Technology, 1993, 8(4): 31-35.
    [10]Huang Xuedong, Cai Lianhong, Fang Ditang, Chi Bianjin, Zhou Li, Jiang Li. A Computer System for Chinese Character Speech Input[J]. Journal of Computer Science and Technology, 1986, 1(4): 75-83.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (16) PDF downloads (1303) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return