On the Problem of How to Place the Observers in Passive Testing

Zhao Baohua, Guo Xionghui, QianLan, and Qu Yugui

Journal of Computer Research and Development > 2005 > 42(10): 1815-1819.

Zhao Baohua, Guo Xionghui, QianLan, and Qu Yugui. On the Problem of How to Place the Observers in Passive Testing[J]. Journal of Computer Research and Development, 2005, 42(10): 1815-1819.

Citation:

Zhao Baohua, Guo Xionghui, QianLan, and Qu Yugui. On the Problem of How to Place the Observers in Passive Testing[J]. Journal of Computer Research and Development, 2005, 42(10): 1815-1819.

Citation:

Zhao Baohua, Guo Xionghui, QianLan, and Qu Yugui. On the Problem of How to Place the Observers in Passive Testing[J]. Journal of Computer Research and Development, 2005, 42(10): 1815-1819.

PDF (287 KB)

On the Problem of How to Place the Observers in Passive Testing

Zhao Baohua, Guo Xionghui, QianLan, and Qu Yugui

(Department of Computer Science and Technology, University of Science and Technology of China, Hefei 230027)

More Information

Published Date: October 14, 2005

Graphical Abstract

Abstract

Abstract

The problem of how to place the observers in passive testing while assuring they can monitor all the behavior of a network and the number of them is the smallest is an interesting and useful problem. First, this problem is proved to be an NP-complete problem. Then a special case in which the topology of network is a tree is discussed and a linear time algorithm for it is presented. Based on the thought of tree topology an improved approximate algorithm is proposed and the approximate proportion of the improved algorithm is 2-O(1). Finally, a simulating experiment is conducted to illustrate the effectiveness of the improved algorithm and future extensions are discussed.
- passive testing,
- NP-complete problem,
- communicating finite state machine

FullText(HTML)

References (0)

[1]	Wang Jianwei, Hao Zhongxiao. Node Probability Query Algorithm in Probabilistic XML Document Tree[J]. Journal of Computer Research and Development, 2012, 49(4): 785-794.
[2]	Meng Xiangfu, Yan Li, Zhang Wengbo, Ma Zongmin. XML Approximate Query Approach Based on Attribute Units Extension[J]. Journal of Computer Research and Development, 2010, 47(11): 1936-1946.
[3]	Liu Xiping, Wan Changxuan, and Liu Dexi. Effective XML Vague Content and Structure Retrieval and Scoring[J]. Journal of Computer Research and Development, 2010, 47(6): 1070-1078.
[4]	Yang Weidong and Shi Baile. A Survey of XML Stream Management[J]. Journal of Computer Research and Development, 2009, 46(10): 1721-1728.
[5]	Wang Xin, Yuan Xiaojie, Wang Chenying, and Zhang Haiwei. XN-Store: A Storage Scheme for Native XML Databases[J]. Journal of Computer Research and Development, 2008, 45(7).
[6]	Wan Jing, Hao Zhongxiao. Study of Multi-Valued Dependency in Strong Total Order Temporal Scheme with Multiple Time Granularities[J]. Journal of Computer Research and Development, 2008, 45(6).
[7]	Wu Yonghui. The Sufficient and Necessary Condition for No Implicit Redundancies in an XML Schema[J]. Journal of Computer Research and Development, 2007, 44(12): 2106-2111.
[8]	Hao Zhongxiao, Li Yanjuan. Normalization of Temporal Scheme with Respect to Temporal Multivalued Dependency with Multiple Time Granularities[J]. Journal of Computer Research and Development, 2007, 44(5): 853-859.
[9]	Lü Teng, Yan Ping. Functional Dependencies and Inference Rules for XML[J]. Journal of Computer Research and Development, 2005, 42(5): 792-796.
[10]	Zhang Zhongping, Wang Chao, Zhu Yangyong. Constraint-Based Normalization Algorithms for XML Documents[J]. Journal of Computer Research and Development, 2005, 42(5): 755-764.