On the Monotonicity of Weak Searching

摘要：

In this paper, we propose and study two digraph searching models: weak searching and mixed weak searching. In these two searching models, each searcher must follow the edge directions when they move along edges, but the intruder can move from tail to head or from head to tail along edges. We prove the monotonicity of the mixed weak searching model by using Bienstock and Seymours method, and prove the monotonicity of the weak searching model by using LaPaughs method. We show that both searching problems are NP-complete.

作者: Boting Yang Yi Cao

作者单位: Department of Computer Science, University of Regina

会议类型: 国际会议

会议名称: The 4th Annual International Computing and Combinatorics Conference,COCOON 2008(第14届国际计算和组合会议)

会议地点: 大连

会议语种:英文

页码: 52-61

在线出版日期: 2008-06-01（万方平台首次上网日期，不代表论文的发表时间）