凸三角多面体的快速搜索
Fast Searching on Convex Deltahedra
DOI: 10.12677/ORF.2018.83015, PDF,   
作者: 韩小东：浙江师范大学数理与信息工程学院，浙江 金华
关键词: 快速搜索；图搜索；追逃对策；警察和小偷博弈；Fast Searching； Graph Searching； Pursuit-Evasion Strategy； Cops and Robber Game
摘要: 本文研究的图搜索模型是快速搜索，该模型与边搜索的区别仅是：搜索者不能“跳跃”且每条边只能被访问一次。本文研究的图是凸三角多面体，求解所有凸三角多面体的快速搜索数，提出关于凸三角多面体快速搜索数的相关推论。
Abstract: In this paper, we study fast searching graph searching model, which differs from the classical edge searching in one way: every edge is traversed exactly once and searchers are not allowed to jump. The graph of this paper is convex deltahedra. We will examine the fast search number (i.e., the minimum number of searchers required for capturing the fugitive) of all the convex deltahedra. We provide an explicit formula for the fast search number of convex deltahedra.
文章引用：韩小东. 凸三角多面体的快速搜索[J]. 运筹与模糊学, 2018, 8(3): 119-126. https://doi.org/10.12677/ORF.2018.83015

参考文献

[1] Breisch, R. (1967) An Intuitive Approach to Speleotopology. Southwestern Cavers, 5, 72-78.
[2] Parsons, T.D. (1978) Pursuit-Evasion in a Graph. Theory and Applications of Graphs, 642, 426-441. [Google Scholar] [CrossRef] 
[3] Kirousis, L.M. and Papadimitriou, C.H. (1986) Searching and Pebbling. Theoretical Computer Science, 47, 205-218. [Google Scholar] [CrossRef] 
[4] Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S. and Papadimitriou, C.H. (1988) The Complexity of Searching a Graph. Association for Computing Machinery, 35, 18-44. [Google Scholar] [CrossRef] 
[5] Dyer, D., Yang, B. and Yaşar, Ö. (2008) On the Fast Searching Prob-lem. AAIM 2008, LNCS, 5034, 143-154. [Google Scholar] [CrossRef] 
[6] Stanley, D. and Yang, B. (2011) Fast Searching Games on Graphs. Journal of Combinatorial Optimization, 22, 763-777. [Google Scholar] [CrossRef] 
[7] Yang, B. (2013) Fast-Mixed Searching and Related Problems on Graph. Theoretical Computer Science, 507, 100-113. [Google Scholar] [CrossRef] 
[8] Xue, Y., Yang, B., Zhong, F. and Zilles, S. (2016) Fast Searching on Complete k-Partite Graphs. Conference on Combinatorial Optimization and Applications, 10043, 159-174. [Google Scholar] [CrossRef] 
[9] Xue, Y. and Yang, B. (2017) The Fast Search Number of a Cartesian Product of Graphs. Discrete Applied Mathematics. [Google Scholar] [CrossRef] 
[10] Dendris, N.D., Kirousis, L.M. and Thilikos, D.M. (1995) Fugi-tive-Search Games on Graphs and Related Parameters. Graph-Theoretic Concepts in Computer Science. Springer, Berlin, Heidelberg. [Google Scholar] [CrossRef] 
[11] Yang, B. and Cao, Y. (2008) Monotonicity in Digraph Search Problems. Theoretical Computer Science, 407, 532-544. [Google Scholar] [CrossRef] 
[12] Richerby, D. and Thilikos, D.M. (2007) Graph Searching in a Crime Wave. International Conference on Graph-Theoretic Concepts in Computer Science, 4769, 21-32. [Google Scholar] [CrossRef] 
[13] Yang, B. (2011) Fast Edge Searching and Fast Searching on Graphs. Theoretical Computer Science, 412, 1208-1219. [Google Scholar] [CrossRef] 
[14] Bonato, A. and Yang, B. (2013) Graph Searching and Related Problems. Handbook of Combinatorial Optimization, 1511-1558. [Google Scholar] [CrossRef] 
[15] Bienstock, D. and Seymour, P. (1991) Monotonicity in Graph Searching. Academic Press, Inc., 239-245.
[16] Lapaugh, A.S. (1993) Recontamination Does Not Help to Search a Graph. Journal of the ACM, 40, 224-245. [Google Scholar] [CrossRef] 
[17] Yang, B., Dyer, D. and Alspach, B. (2009) Sweeping Graphs with Large Clique Number. Elsevier Science Publishers B. V.
[18] Flocchini, P., Fraigniaud, P. and Santoro, N. (2002) Capture of an Intruder by Mobile Agents. ACM, 200-209.
[19] Kinnersley, N.G. (1992) The Vertex Separation Number of a Graph Equals Its Path-Width. Information Processing Letters, 42, 345-350. [Google Scholar] [CrossRef] 
[20] Isaza, A., Lu, J., Bulitko, V., et al. (2008) A Cover-Based Approach to Multi-Agent Moving Target Pursuit. Artificial Intelligence and Interactive Digital Entertainment Conference, Stanford, California, 22-24 October 2008, 54-59.
[21] Moldenhauer, C. and Sturtevant, N.R. (2009) Evaluating Strategies for Running from the Cops. International Joint Conference on Artificial Intelligence, Morgan Kaufmann Publishers Inc., 584-589.

为你推荐