{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,27]],"date-time":"2026-10-27T18:47:40Z","timestamp":1793126860434,"version":"4.5.0"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We study the following pursuit-evasion game: One or more hunters are seeking to capture an evading rabbit on a graph. At each round, the rabbit tries to gather information about the location of the hunters but it can see them only if they are located on adjacent nodes. We show that two hunters suffice for catching rabbits with such local visibility with high probability. We distinguish between reactive rabbits who move only when a hunter is visible and general rabbits who can employ more sophisticated strategies. We present polynomial time algorithms that decide whether a graph G is hunter-win, that is, if a single hunter can capture a rabbit of either kind on G.<\/jats:p>","DOI":"10.1137\/s0895480104442169","type":"journal-article","created":{"date-parts":[[2006,2,23]],"date-time":"2006-02-23T21:00:22Z","timestamp":1140728422000},"page":"26-41","source":"Crossref","is-referenced-by-count":62,"title":["Randomized Pursuit-Evasion with Local Visibility"],"prefix":"10.1137","volume":"20","author":[{"given":"Volkan","family":"Isler","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sampath","family":"Kannan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"MicahAdler, HaraldR\u00e4cke, NaveenSivadasan, ChristianSohler, BertholdV\u00f6cking, Randomized pursuit\u2010evasion in graphs, Lecture Notes in Comput. Sci., Vol. 2380, Springer, Berlin, 2002, 901\u2013912MR2062517","DOI":"10.1007\/3-540-45465-9_77"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90073-8"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(87)90107-6"},{"key":"R4","volume-title":"Dynamic noncooperative game theory","author":"Ba\u015far Tamer","year":"1999"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(87)90105-2"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1935"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1064"},{"key":"R8","first-page":"65","volume":"59","author":"Fitzpatrick Shannon","year":"2001","journal-title":"Ars Combin."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195999000273"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"J. P. Hespanha, G. J. Pappas, and M. Prandini,\n                      Greedy control for hybrid pursuit\u2010evasion games\n                      , in Proceedings of the European Control Conference, Porto, Portugal, 2001, pp. 2621\u20132626.","DOI":"10.23919\/ECC.2001.7076324"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"I. Chatzigiannakis, S. Nikoletseas, and P. Spirakis,\n                      An efficient communication strategy for ad\u2010hoc mobile networks\n                      , in Proceedings of the 15th Symposium on Distributed Computing (DISC\u20192001), University of Lisbon, Lisbon, Portugal, 2001, pp. 285\u2013299.","DOI":"10.1007\/3-540-45414-4_20"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1145\/151261.151263"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1145\/42267.42268"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(97)00165-9"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90160-7"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Sang\u2010MinPark, Jae\u2010HaLee, Kyung\u2010YongChwa, Visibility\u2010based pursuit\u2010evasion in a polygonal region by a searcher, Lecture Notes in Comput. Sci., Vol. 2076, Springer, Berlin, 2001, 456\u2013468MR2066525","DOI":"10.1007\/3-540-48224-5_38"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"T.Parsons, Pursuit\u2010evasion in a graph, Springer, Berlin, 1978, 0\u20130, 426\u2013441. Lecture Notes in Math., Vol. 64258:10622","DOI":"10.1007\/BFb0070400"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2002.804040"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480104442169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:10:58Z","timestamp":1787321458000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480104442169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0895480104442169"],"URL":"https:\/\/doi.org\/10.1137\/s0895480104442169","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}