{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T03:38:14Z","timestamp":1725507494727},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540770954"},{"type":"electronic","value":"9783540770961"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77096-1_30","type":"book-chapter","created":{"date-parts":[[2008,4,11]],"date-time":"2008-04-11T11:44:46Z","timestamp":1207914286000},"page":"415-428","source":"Crossref","is-referenced-by-count":1,"title":["The Cost of Monotonicity in Distributed Graph\u00a0Searching"],"prefix":"10.1007","author":[{"given":"David","family":"Ilcinkas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Soguet","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","first-page":"200","volume-title":"14th ACM Symp. on Parallel Algorithms and Architectures (SPAA)","author":"L. Barri\u00e8re","year":"2002","unstructured":"Barri\u00e8re, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: 14th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 200\u2013209. ACM Press, New York (2002)"},{"key":"30_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/978-3-540-39890-5_4","volume-title":"In 29th Workshop on Graph Theoretic Concepts in Computer Science (WG)","author":"L. Barri\u00e8re","year":"2003","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Santoro, N., Thilikos, D.: Connected and Internal Graph Searching. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 34\u201345. Springer, Heidelberg (2003)"},{"doi-asserted-by":"crossref","unstructured":"Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey) DIMACS Ser. in Discrete Mathematics and Theoretical Computer Science, 5, pp. 33\u201349 (1991)","key":"30_CR3","DOI":"10.1090\/dimacs\/005\/02"},{"key":"30_CR4","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D., Seymour, P.: Monotonicity in graph searching. Journal of Algorithms\u00a012, 239\u2013245 (1991)","journal-title":"Journal of Algorithms"},{"key":"30_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/11780823_7","volume-title":"In 13th Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"L. Blin","year":"2006","unstructured":"Blin, L., Fraigniaud, P., Nisse, N., Vial, S.: Distributing Chasing of Network Intruders. In: Flocchini, P., G\u0105sieniec, L. (eds.) SIROCCO 2006. LNCS, vol.\u00a04056, pp. 70\u201384. Springer, Heidelberg (2006)"},{"key":"30_CR6","first-page":"72","volume":"5","author":"R. Breisch","year":"1967","unstructured":"Breisch, R.: An intuitive approach to speleotopology. Southwestern Cavers\u00a05, 72\u201378 (1967)","journal-title":"Southwestern Cavers"},{"doi-asserted-by":"crossref","unstructured":"Flocchini, P., Luccio, F.L., Song, L.: Decontamination of chordal rings and tori. In: Proc. of 8th Workshop on Advances in Parallel and Distributed Computational Models (APDCM) (2006)","key":"30_CR7","DOI":"10.1109\/IPDPS.2006.1639545"},{"unstructured":"Flocchini, P., Luccio, F.L., Song, L.: Size Optimal Strategies for Capturing an Intruder in Mesh Networks. In: Proceedings of the 2005 International Conference on Communications in Computing (CIC), pp. 200\u2013206 (2005)","key":"30_CR8"},{"key":"30_CR9","volume-title":"Proc. of 18th IEEE Int. Parallel and Distributed Processing Symp. (IPDPS)","author":"P. Flocchini","year":"2005","unstructured":"Flocchini, P., Huang, M.J., Luccio, F.L.: Contiguous search in the hypercube for capturing an intruder. In: Proc. of 18th IEEE Int. Parallel and Distributed Processing Symp (IPDPS), IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"30_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"470","DOI":"10.1007\/11682462_45","volume-title":"In 7th Latin American Theoretical Informatics Symp. (LATIN)","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Nisse, N.: Connected Treewidth and Connected Graph Searching. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 470\u2013490. Springer, Heidelberg (2006)"},{"key":"30_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/11917496_21","volume-title":"In 32th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"P. Fraigniaud","year":"2006","unstructured":"Fraigniaud, P., Nisse, N.: Monotony properties of connected visible graph searching. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 229\u2013240. Springer, Heidelberg (2006)"},{"unstructured":"Ilcinkas, D., Nisse, N., Soguet, D.: The cost of monotonicity in distributed graph\u00a0searching. Technical Report, LRI-1475, University Paris-Sud, France (September 2007)","key":"30_CR12"},{"issue":"2","key":"30_CR13","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A. LaPaugh","year":"1993","unstructured":"LaPaugh, A.: Recontamination does not help to search a graph. Journal of the ACM\u00a040(2), 224\u2013245 (1993)","journal-title":"Journal of the ACM"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-540-72914-3_22","volume-title":"FUN 2007","author":"F.L. Luccio","year":"2007","unstructured":"Luccio, F.L.: Intruder capture in Sierpinski graphs. In: Crescenzi, P., Prencipe, G., Pucci, G. (eds.) FUN 2007. LNCS, vol.\u00a04475, pp. 249\u2013261. Springer, Heidelberg (2007)"},{"issue":"1","key":"30_CR15","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Hakimi, S., Garey, M., Johnson, D., Papadimitriou, C.: The complexity of searching a graph. Journal of the ACM\u00a035(1), 18\u201344 (1988)","journal-title":"Journal of the ACM"},{"key":"30_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/978-3-540-72951-8_6","volume-title":"SIROCCO 2007","author":"N. Nisse","year":"2007","unstructured":"Nisse, N., Soguet, D.: Graph searching with advice. In: Prencipe, G., Fales, S. (eds.) SIROCCO 2007. 14th Colloquium on Structural Information and Communication Complexity. LNCS, vol.\u00a04474, pp. 51\u201367. Springer, Heidelberg (2007)"},{"key":"30_CR17","first-page":"426","volume-title":"Theory and Applications of Graphs","author":"T. Parson","year":"1976","unstructured":"Parson, T.: Pursuit-evasion in a graph. In: Parson, T. (ed.) Theory and Applications of Graphs. Lecture Notes in Mathematics, pp. 426\u2013441. Springer, Heidelberg (1976)"},{"key":"30_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"908","DOI":"10.1007\/978-3-540-30551-4_77","volume-title":"In 15th Annual International Symp. on Algorithms and Computation (ISAAC)","author":"B. Yang","year":"2004","unstructured":"Yang, B., Dyer, D., Alspach, B.: Sweeping Graphs with Large Clique Number. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 908\u2013920. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Principles of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77096-1_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:00:11Z","timestamp":1619521211000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77096-1_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540770954","9783540770961"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77096-1_30","relation":{},"subject":[]}}