{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:18:54Z","timestamp":1759637934525},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319252575"},{"type":"electronic","value":"9783319252582"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25258-2_24","type":"book-chapter","created":{"date-parts":[[2015,10,19]],"date-time":"2015-10-19T03:10:18Z","timestamp":1445224218000},"page":"342-356","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds for the Capture Time: Linear, Quadratic, and Beyond"],"prefix":"10.1007","author":[{"given":"Klaus-Tycho","family":"F\u00f6rster","sequence":"first","affiliation":[]},{"given":"Rijad","family":"Nuridini","sequence":"additional","affiliation":[]},{"given":"Jara","family":"Uitto","sequence":"additional","affiliation":[]},{"given":"Roger","family":"Wattenhofer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,20]]},"reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0166-218X(84)90073-8","volume":"8","author":"M. Aigner","year":"1984","unstructured":"Aigner, M., Fromme, M.: A Game of Cops and Robbers. Discrete Applied Mathematics\u00a08(1), 1\u201312 (1984)","journal-title":"Discrete Applied Mathematics"},{"key":"24_CR2","first-page":"5","volume":"59","author":"B. Alspach","year":"2006","unstructured":"Alspach, B.: Sweeping and Searching in Graphs: a Brief Survey. Matematiche\u00a059, 5\u201337 (2006)","journal-title":"Matematiche"},{"issue":"4","key":"24_CR3","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1006\/aama.1993.1019","volume":"14","author":"A. Berarducci","year":"1993","unstructured":"Berarducci, A., Intrigila, B.: On the Cop Number of a Graph. Advances in Applied Mathematics\u00a014(4), 389\u2013403 (1993)","journal-title":"Advances in Applied Mathematics"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Bonato, A., Chiniforooshan, E.: Pursuit and evasion from a distance: algorithms and bounds. In: Proceedings of the Sixth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), pp. 1\u201310. SIAM (2009)","DOI":"10.1137\/1.9781611972993.1"},{"issue":"18","key":"24_CR5","doi-asserted-by":"publisher","first-page":"5588","DOI":"10.1016\/j.disc.2008.04.004","volume":"309","author":"A. Bonato","year":"2009","unstructured":"Bonato, A., Golovach, P.A., Hahn, G., Kratochv\u00edl, J.: The Capture Time of a Graph. Discrete Mathematics\u00a0309(18), 5588\u20135595 (2009)","journal-title":"Discrete Mathematics"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Bonato, A., Gordinowicz, P., Kinnersley, B., Pra\u0142at, P.: The Capture Time of the Hypercube. Electr. J. Comb.\u00a020(2), P24 (2013)","DOI":"10.37236\/2921"},{"key":"24_CR7","series-title":"Student Mathematical Library","doi-asserted-by":"crossref","DOI":"10.1090\/stml\/061","volume-title":"The Game of Cops and Robbers on Graphs","author":"A. Bonato","year":"2011","unstructured":"Bonato, A., Nowakowski, R.J.: The Game of Cops and Robbers on Graphs. Student Mathematical Library, vol.\u00a061. American Mathematical Society, Providence (2011)"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"1511","DOI":"10.1007\/978-1-4419-7997-1_76","volume-title":"Handbook of Combinatorial Optimization","author":"A. Bonato","year":"2013","unstructured":"Bonato, A., Yang, B.: Graph searching and related problems. In: Handbook of Combinatorial Optimization, pp. 1511\u20131558. Springer, New York (2013)"},{"issue":"5","key":"24_CR9","first-page":"72","volume":"6","author":"R. Breisch","year":"1967","unstructured":"Breisch, R.: An Intuitive Approach to Speleotopology. Southwestern Cavers\u00a06(5), 72\u201378 (1967)","journal-title":"Southwestern Cavers"},{"issue":"8","key":"24_CR10","doi-asserted-by":"publisher","first-page":"1421","DOI":"10.1016\/j.disc.2012.01.002","volume":"312","author":"N.E. Clarke","year":"2012","unstructured":"Clarke, N.E., MacGillivray, G.: Characterizations of k-copwin Graphs. Discrete Mathematics\u00a0312(8), 1421\u20131425 (2012)","journal-title":"Discrete Mathematics"},{"key":"24_CR11","unstructured":"Deo, N., Nikoloski, Z.: The Game of Cops and Robbers on Graphs: a Model for Quarantining Cyber Attacks. Congressus Numerantium, 193\u2013216 (2003)"},{"issue":"3","key":"24_CR12","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0166-218X(87)90033-3","volume":"17","author":"P. Frankl","year":"1987","unstructured":"Frankl, P.: Cops and Robbers in Graphs with Large Girth and Cayley Graphs. Discrete Appl. Math.\u00a017(3), 301\u2013305 (1987)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"24_CR13","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1002\/jgt.20591","volume":"69","author":"A.M. Frieze","year":"2012","unstructured":"Frieze, A.M., Krivelevich, M., Loh, P.-S.: Variations on Cops and Robbers. Journal of Graph Theory\u00a069(4), 383\u2013402 (2012)","journal-title":"Journal of Graph Theory"},{"issue":"10\u201311","key":"24_CR14","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1016\/j.disc.2010.01.015","volume":"310","author":"T. Gavenciak","year":"2010","unstructured":"Gavenciak, T.: Cop-win Graphs with Maximum Capture-time. Discrete Mathematics\u00a0310(10\u201311), 1557\u20131563 (2010)","journal-title":"Discrete Mathematics"},{"issue":"163","key":"24_CR15","first-page":"163","volume":"36","author":"G. Hahn","year":"2007","unstructured":"Hahn, G.: Cops, Robbers and Graphs. Tatra Mt. Math. Publ.\u00a036(163), 163\u2013176 (2007)","journal-title":"Tatra Mt. Math. Publ."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/j.jctb.2014.11.002","volume":"111","author":"W.B. Kinnersley","year":"2015","unstructured":"Kinnersley, W.B.: Cops and Robbers is EXPTIME-complete. J. Comb. Theory, Ser. B\u00a0111, 201\u2013220 (2015)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"24_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/978-3-642-31585-5_54","volume-title":"Automata, Languages, and Programming","author":"A. Kosowski","year":"2012","unstructured":"Kosowski, A., Li, B., Nisse, N., Suchan, K.: k-Chordal graphs: from cops and robber to compact routing via treewidth. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part II. LNCS, vol.\u00a07392, pp. 610\u2013622. Springer, Heidelberg (2012)"},{"issue":"2","key":"24_CR18","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1002\/jgt.20642","volume":"71","author":"L. Lu","year":"2012","unstructured":"Lu, L., Peng, X.: On Meyniel\u2019s Conjecture of the Cop Number. Journal of Graph Theory\u00a071(2), 192\u2013205 (2012)","journal-title":"Journal of Graph Theory"},{"issue":"1","key":"24_CR19","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.disc.2010.10.002","volume":"311","author":"A. Mehrabian","year":"2011","unstructured":"Mehrabian, A.: The Capture Time of Grids. Discrete Mathematics\u00a0311(1), 102\u2013105 (2011)","journal-title":"Discrete Mathematics"},{"issue":"3","key":"24_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1307\/mmj\/1028999370","volume":"12","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W.: On the Diameter of a Graph. Michigan Math. J.\u00a012(3), 349\u2013351 (1965)","journal-title":"Michigan Math. J."},{"issue":"2-3","key":"24_CR21","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0012-365X(83)90160-7","volume":"43","author":"R.J. Nowakowski","year":"1983","unstructured":"Nowakowski, R.J., Winkler, P.: Vertex-to-vertex Pursuit in a Graph. Discrete Mathematics\u00a043(2-3), 235\u2013239 (1983)","journal-title":"Discrete Mathematics"},{"key":"24_CR22","series-title":"Lecture Notes in Computer Science","first-page":"426","volume-title":"Analogical and Inductive Inference","author":"T.D. Parsons","year":"1992","unstructured":"Parsons, T.D.: Pursuit-evasion in a graph. In: Alavi, Y., Lick, D.R. (eds.) AII 1992. LNCS, vol.\u00a0642, pp. 426\u2013441. Springer, Heidelberg (1992)"},{"key":"24_CR23","unstructured":"Parsons, T.D.: The search number of a connected graph. In: Proc. 9th Southeast. Conf. on Combinatorics, Graph Theory, and Computing (1978)"},{"key":"24_CR24","first-page":"285","volume":"46","author":"P. Pra\u0142at","year":"2010","unstructured":"Pra\u0142at, P.: When Does a Random Graph Have a Constant Cop Number. Australasian Journal of Combinatorics\u00a046, 285\u2013296 (2010)","journal-title":"Australasian Journal of Combinatorics"},{"key":"24_CR25","unstructured":"Quilliot, A.: Jeux et Pointes Fixes sur les Graphes. Ph.D. thesis, Universite de Paris VI (1978)"},{"issue":"3","key":"24_CR26","doi-asserted-by":"publisher","first-page":"1438","DOI":"10.1137\/100812963","volume":"25","author":"A. Scott","year":"2011","unstructured":"Scott, A., Sudakov, B.: A Bound for the Cops and Robbers Problem. SIAM J. Discrete Math.\u00a025(3), 1438\u20131442 (2011)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25258-2_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,9]],"date-time":"2020-09-09T19:28:46Z","timestamp":1599679726000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25258-2_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319252575","9783319252582"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25258-2_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}