• Articles • Previous Articles     Next Articles

Decision Tree Complexity of Graph Properties with Dimension at Most5

GAO Suixiang; LIN Guohui;   

  1. 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;
  • Online:2000-09-10 Published:2000-09-10

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…

Key words: data dissemination; gossip; network coding; sensor networks;

[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. ……….
[1] Yuan-Yuan Xu, Ce Zhu, and Lu Yu. Multipath Routing of Multiple Description Coded Images in Wireless Networks [J]. , 2014, 29(4): 576-588.
[2] Xiao-Long Zheng and Meng Wan. A Survey on Data Dissemination in Wireless Sensor Networks [J]. , 2014, 29(3): 470-486.
[3] Mo Chen, (陈默), Student Member, CCF, ACM Ge Yu, (于戈), Senior Member, CCF, Member, ACM, IEEE, Yu Gu (谷峪), Member, CCF, ACM. An Efficient Method for Cleaning Dirty-Events over Uncertain Data in WSNs [J]. , 2011, 26(6): 942-953.
[4] Xiu-Li Ma (马秀莉), Hai-Feng Hu (胡海峰), Shuang-Feng Li (李双峰), Hong-Mei Xiao (肖红梅), Qiong Luo (罗琼), Dong-Qing Yang (杨冬青), Member,CCF, and Shi-Wei Tang (唐世渭), Senior Member, CCF. DHC: Distributed, Hierarchical Clustering in Sensor Networks [J]. , 2011, 26(4): 643-662.
[5] Yu Gu(谷雨), Bao-Hua Zhao(赵保华), Yu-Sheng Ji(计宇生), Member, IEEE, and Jie Li(李颉), Senior Member, ACM, IEEE. Theoretical Treatment of Target Coverage in Wireless Sensor Networks [J]. , 2011, 26(1): 117-129.
[6] Yunhao Liu, Member, ACM, Senior Member, IEEE, Zheng Yang, Student Member, ACM, IEEE, Xiaoping Wang, Student Member, IEEE, and Lirong Jian, Student Member, IEEE. Location, Localization, and Localizability [J]. , 2010, 25(2): 274-297.
[7] Xiao-Lin Li and Jian-Nong Cao. Coordinated Workload Scheduling in Hierarchical Sensor Networks for Data Fusion Applications [J]. , 2008, 23(3): 355-364 .
[8] Feng Lu, Liang-Tien Chia, Kok-Leong Tay, and Wai-Hoe Chong. NBgossip: An Energy-Efficient Gossip Algorithm for Wireless Sensor Networks [J]. , 2008, 23(3): 426-437 .
[9] Jing Zhou and David De Roure. FloodNet: Coupling Adaptive Sampling with Energy Aware Routing in a Flood Warning System [J]. , 2007, 22(1): 121-130 .
[10] Liu-Sheng Huang, Hong-Li Xu, Yang Wang, Jun-Min Wu, and Hong Li. Coverage and Exposure Paths in Wireless Sensor Networks [J]. , 2006, 21(4): 490-495 .
Full text



[1] Fei Xianglin; Liao Lei; Wang Hezhen; Wang Chengzao;. Structured Development Environment Based on the Object-Oriented Concepts[J]. , 1992, 7(3): 193 -201 .
[2] Xu Qingyun; Wang Nengbin;. Concurrency Control Mechanism of Complex Objects[J]. , 1992, 7(4): 305 -310 .
[3] Ma Guangsheng; Zhang Zhongwei; and Huang Shaobin;. A New Method of Solving Kernels in Algebraic Decomposition for the Synthesis of Logic Cell Array[J]. , 1995, 10(6): 569 -573 .
[4] Hui-Xuan Tang and Hui Wei. A Coarse-to-Fine Method for Shape Recognition[J]. , 2007, 22(2): 329 -333 .
[5] Hong-Jie Dai, Yen-Ching Chang, Richard Tzong-Han Tsai, and Wen-Lian Hsu, Fellow, IEEE. New Challenges for Biological Text-Mining in the Next Decade[J]. , 2010, 25(1): 169 -inside back cover .
[6] Yue-Hua Wang (王跃华), Student Member, IEEE, Zhong Zhou (周忠), Member, CCF, ACM, IEEE, Ling Liu, Senior Member, IEEE, and Wei Wu (吴威), Member, CCF. Fault Tolerance and Recovery for Group Communication Services in Distributed Networks[J]. , 2012, (2): 298 -312 .
[7] Mohamed El Bachir Menai and Tasniem Nasser Al-Yahya. A Taxonomy of Exact Methods for Partial Max-SAT[J]. , 2013, 28(2): 232 -246 .
[8] Wu Yang Guo-Wei Shen, Wei Wang, Liang-Yi Gong, Miao Yu, Guo-Zhong Dong. Anomaly Detection in Microblogging via Co-Clustering[J]. , 2015, 30(5): 1097 -1108 .
[9] Can Cheng, Bing Li, Zeng-Yang Li, Yu-Qi Zhao, Feng-Ling Liao. Developer Role Evolution in Open Source Software Ecosystem: An Explanatory Study on GNOME[J]. , 2017, 32(2): 396 -414 .
[10] You-Xi Wu, Dong Liu, He Jiang. Length-Changeable Incremental Extreme Learning Machine[J]. , 2017, 32(3): 630 -643 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved