{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T16:11:34Z","timestamp":1764173494799},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540688655"},{"type":"electronic","value":"9783540688808"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-68880-8_15","type":"book-chapter","created":{"date-parts":[[2008,7,31]],"date-time":"2008-07-31T06:37:59Z","timestamp":1217486279000},"page":"143-154","source":"Crossref","is-referenced-by-count":19,"title":["On the Fast Searching Problem"],"prefix":"10.1007","author":[{"given":"Danny","family":"Dyer","sequence":"first","affiliation":[]},{"given":"Boting","family":"Yang","sequence":"additional","affiliation":[]},{"given":"\u00d6znur","family":"Ya\u015far","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/978-3-540-74450-4_46","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"B. Alspach","year":"2007","unstructured":"Alspach, B., Dyer, D., Hanson, D., Yang, B.: Lower bounds on edge searching. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 516\u2013527. Springer, Heidelberg (2007)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Barri\u00e8re, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: Proceedings of the 14th annual ACM symposium on Parallel algorithms and architectures (SPAA 2002), pp. 200\u2013209 (2002)","DOI":"10.1145\/564905.564906"},{"key":"15_CR3","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":"Graph-Theoretic Concepts in Computer Science","author":"L. Barri\u00e8re","year":"2003","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Santoro, N., Thilikos, D.: Searching is not Jumping. In: Bodlaender, H.L. (ed.) WG 2003. LNCS, vol.\u00a02880, pp. 34\u201345. Springer, Heidelberg (2003)"},{"key":"15_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":"15_CR5","first-page":"72","volume":"6","author":"R.L. Breisch","year":"1967","unstructured":"Breisch, R.L.: An intuitive approach to speleotopology. Southwestern Cavers\u00a06, 72\u201378 (1967)","journal-title":"Southwestern Cavers"},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/0606026","volume":"6","author":"F. Chung","year":"1985","unstructured":"Chung, F.: On the cutwidth and the topological bandwidth of a tree. SIAM J. Algebraic Discrete Methods\u00a06, 268\u2013277 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"15_CR7","doi-asserted-by":"publisher","first-page":"454","DOI":"10.1137\/S0895480199350477","volume":"13","author":"F.V. Fomin","year":"2000","unstructured":"Fomin, F.V., Golovach, P.A.: Interval completion and graph searching. SIAM Journal on Discrete Mathematics\u00a013, 454\u2013464 (2000)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theoretical Computer Science, Special Issue on Graph Searching (submitted on November 2007)","DOI":"10.1016\/j.tcs.2008.02.034"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The Vertex Separation Number of a graph equals its path-width. Information Processing Letters\u00a042, 345\u2013350 (1992)","journal-title":"Information Processing Letters"},{"key":"15_CR10","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A.S. LaPaugh","year":"1993","unstructured":"LaPaugh, A.S.: Recontamination does not help to search a graph. Journal of ACM\u00a040, 224\u2013245 (1993)","journal-title":"Journal of ACM"},{"key":"15_CR11","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Hakimi, S.L., Garey, M.R., Johnson, D.S., Papadimitriou, C.H.: The Complexity of Searching a Graph. Journal of ACM\u00a035, 18\u201344 (1988)","journal-title":"Journal of ACM"},{"key":"15_CR12","series-title":"Lecture Notes in Mathematics","first-page":"426","volume-title":"Theory and Applications of Graphs","author":"T. Parsons","year":"1976","unstructured":"Parsons, T.: Pursuit-evasion in a graph. In: Theory and Applications of Graphs. Lecture Notes in Mathematics, pp. 426\u2013441. Springer, Heidelberg (1976)"},{"key":"15_CR13","volume-title":"Introduction to Graph Theory","author":"D.B. West","year":"1996","unstructured":"West, D.B.: Introduction to Graph Theory. Prentice Hall, Englewood Cliffs (1996)"},{"key":"15_CR14","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":"Algorithms and Computation","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","Algorithmic Aspects in Information and Management"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-68880-8_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:16:59Z","timestamp":1620015419000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-68880-8_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540688655","9783540688808"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-68880-8_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}