{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T03:25:46Z","timestamp":1763436346232},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540204527"},{"type":"electronic","value":"9783540398905"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39890-5_4","type":"book-chapter","created":{"date-parts":[[2010,9,3]],"date-time":"2010-09-03T21:16:57Z","timestamp":1283548617000},"page":"34-45","source":"Crossref","is-referenced-by-count":31,"title":["Searching Is Not Jumping"],"prefix":"10.1007","author":[{"given":"Lali","family":"Barri\u00e8re","sequence":"first","affiliation":[]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","doi-asserted-by":"crossref","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 2002), Winnipeg, August 10-13 (2002)","DOI":"10.1145\/564870.564906"},{"key":"4_CR2","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Santoro, N., Thilikos, D.M.: Connected and Internal Graph Searching. Technical Report LSI-02-58-R, Universitat Polit\u00e8cnica de Catalunya, Barcelona, Spain (2002), http:\/\/www.lsi.upc.es\/~sedthilk"},{"key":"4_CR3","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","volume":"5","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: Graph searching, path-width, tree-width and related problems. DIMACS Series in Disc. Maths. and Theo. Comp. Sc.\u00a05, 33\u201349 (1991)","journal-title":"DIMACS Series in Disc. Maths. and Theo. Comp. Sc."},{"key":"4_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"},{"issue":"5","key":"4_CR5","first-page":"72","volume":"VI","author":"R. Breisch","year":"1967","unstructured":"Breisch, R.: An intuitive approach to speleotopology. Southwestern Cavers\u00a0VI(5), 72\u201378 (1967)","journal-title":"Southwestern Cavers"},{"issue":"1","key":"4_CR6","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J. Ellis","year":"1994","unstructured":"Ellis, J., Sudborough, H., Turner, J.: The vertex separation and search number of a graph. Information and Computation\u00a0113(1), 50\u201379 (1994)","journal-title":"Information and Computation"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Fellows, M., Langston, M.: On search, decision and the efficiency of polynomial time algorithm. In: 21st ACM Symp. on Theory of Computing (STOC 1989), pp. 501\u2013512 (1989)","DOI":"10.1145\/73007.73055"},{"key":"4_CR8","unstructured":"Fomin, F., Thilikos, D.M.: On the monotonicity of games generated by symmetric submodular functions. Discrete Applied Mathematics (to appear)"},{"issue":"2","key":"4_CR9","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/333979.333980","volume":"47","author":"M. Franklin","year":"2000","unstructured":"Franklin, M., Galil, Z., Yung, M.: Eavesdropping games: a graph theoretic approach to privacy in distributed systems. Journal of the ACM\u00a047(2), 225\u2013243 (2000)","journal-title":"Journal of the ACM"},{"issue":"2","key":"4_CR10","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":"4_CR11","doi-asserted-by":"crossref","unstructured":"Linial, N., Magen, A., Saks, M.: Trees and Euclidian metrics. In: 30st ACM Symp. on Theory of Computing (STOC 1998), pp. 169\u2013175 (1998)","DOI":"10.1145\/276698.276726"},{"key":"4_CR12","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/BF02785579","volume":"114","author":"J. Matousek","year":"1999","unstructured":"Matousek, J.: On embedding trees into uniformly convex Banach spaces. Israelian Journal of Mathematics\u00a0114, 221\u2013237 (1999)","journal-title":"Israelian Journal of Mathematics"},{"key":"4_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/BFb0036931","volume-title":"Automata, Languages and Programming","author":"F. Makedon","year":"1983","unstructured":"Makedon, F., Sudborough, H.: Minimizing width in linear layouts. In: D\u00edaz, J. (ed.) ICALP 1983. LNCS, vol.\u00a0154, pp. 478\u2013490. Springer, Heidelberg (1983)"},{"issue":"1","key":"4_CR14","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":"4_CR15","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":"4_CR16","unstructured":"Parsons, T.: The search number of a connected graph. In: 9th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, pp. 549\u2013554 (1978)"},{"key":"4_CR17","first-page":"153","volume-title":"Surveys in Combinatorics","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.: Graph minors \u2014 A survey. In: Anderson, I. (ed.) Surveys in Combinatorics, pp. 153\u2013171. Cambridge University Press, Cambridge (1985)"},{"key":"4_CR18","first-page":"239","volume":"58","author":"P. Seymour","year":"1993","unstructured":"Seymour, P., Thomas, R.: Graph searching, and a min-max theorem for treewidth. Jour. Combin. Theory, Ser. B\u00a058, 239\u2013257 (1993)","journal-title":"Jour. Combin. Theory, Ser. B"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/3-540-45253-2_37","volume-title":"Algorithms - ESA 2000","author":"K. Skodinis","year":"2000","unstructured":"Skodinis, K.: Computing optimal linear layouts of trees in linear time. In: Paterson, M. (ed.) ESA 2000. LNCS, vol.\u00a01879, pp. 403\u2013414. Springer, Heidelberg (2000)"},{"issue":"1-3","key":"4_CR20","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(94)90092-2","volume":"127","author":"A. Takahashi","year":"1994","unstructured":"Takahashi, A., Ueno, S., Kajitani, Y.: Minimal acyclic forbidden minors for the family of graphs with bounded path-width. Discrete Mathematics\u00a0127(1-3), 293\u2013304 (1994)","journal-title":"Discrete Mathematics"},{"key":"4_CR21","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(00)00175-X","volume":"105","author":"D. Thilikos","year":"2000","unstructured":"Thilikos, D.: Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics\u00a0105, 239\u2013271 (2000)","journal-title":"Discrete Applied Mathematics"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39890-5_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,3]],"date-time":"2019-06-03T09:18:55Z","timestamp":1559553535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39890-5_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540204527","9783540398905"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39890-5_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}