{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:42:39Z","timestamp":1786981359160,"version":"build-2736575974"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2007,9,27]]},"DOI":"10.1007\/s10878-007-9042-z","type":"journal-article","created":{"date-parts":[[2007,3,20]],"date-time":"2007-03-20T11:51:20Z","timestamp":1174391480000},"page":"411-425","source":"Crossref","is-referenced-by-count":7,"title":["Monotonicity of strong searching on digraphs"],"prefix":"10.1007","volume":"14","author":[{"given":"Boting","family":"Yang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yi","family":"Cao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"9042_CR1","doi-asserted-by":"crossref","unstructured":"Adler I (2007) Directed tree-width examples. J Comb Theory Ser B (to appear)","DOI":"10.1016\/j.jctb.2006.12.006"},{"key":"9042_CR2","unstructured":"Alspach B (2005) Searching and searching graphs: a brief survey. Le Matematiche"},{"key":"9042_CR3","unstructured":"Alspach B, Dyer D, Hanson D, Yang B (2006) Some basic results in arc searching. Technical report CS-2006-10, Department of Computer Science, University of Regina"},{"key":"9042_CR4","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s00373-005-0627-y","volume":"22","author":"J Barat","year":"2006","unstructured":"Barat J (2006) Directed path-width and monotonicity in digraph searching. Graphs Comb 22:161\u2013172","journal-title":"Graphs Comb"},{"key":"9042_CR5","doi-asserted-by":"crossref","unstructured":"Berwanger D, Dawar A, Hunter P, Kreutzer S (2006) DAG-width and parity games. In: Proceedings of the 23rd annual symposium on theoretical aspects of computer science (STACS 2006). Lecture notes in computer science, vol\u00a03884, pp 524\u2013436","DOI":"10.1007\/11672142_43"},{"key":"9042_CR6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","volume":"5","author":"D Bienstock","year":"1991","unstructured":"Bienstock D (1991) Graph searching path-width, tree-width and related problems (a survey). DIMACS Ser Discret Math Theor Comput Sci 5:33\u201349","journal-title":"DIMACS Ser Discret Math Theor Comput Sci"},{"key":"9042_CR7","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D Bienstock","year":"1991","unstructured":"Bienstock D, Seymour P (1991) Monotonicity in graph searching. J Algorithms 12:239\u2013245","journal-title":"J Algorithms"},{"key":"9042_CR8","first-page":"72","volume":"6","author":"RL Breisch","year":"1967","unstructured":"Breisch RL (1967) An intuitive approach to speleotopology. Southwest Cavers 6:72\u201378","journal-title":"Southwest Cavers"},{"key":"9042_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1016\/S0304-3975(96)00177-6","volume":"172","author":"N Dendris","year":"1997","unstructured":"Dendris N, Kirousis L, Thilikos D (1997) Fugitive-search games on graphs and related parameters. Theor Comput Sci 172:233\u2013254","journal-title":"Theor Comput Sci"},{"key":"9042_CR10","doi-asserted-by":"crossref","unstructured":"Fellows M, Langston M (1989) On search, decision and the efficiency of polynomial time algorithm. In: Proceedings of the 21st ACM symposium on theory of computing (STOC 89), pp\u00a0501\u2013512","DOI":"10.1145\/73007.73055"},{"key":"9042_CR11","first-page":"47","volume":"122","author":"F Fomin","year":"1996","unstructured":"Fomin F, Petrov N (1996) Pursuit-evasion and search problems on graphs. Congr Numer 122:47\u201358","journal-title":"Congr Numer"},{"key":"9042_CR12","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0166-218X(02)00459-6","volume":"131","author":"F Fomin","year":"2003","unstructured":"Fomin F, Thilikos D (2003) On the monotonicity of games generated by symmetric submodular functions. Discret Appl Math 131:323\u2013335","journal-title":"Discret Appl Math"},{"key":"9042_CR13","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/333979.333980","volume":"47","author":"M Frankling","year":"2000","unstructured":"Frankling M, Galil Z, Yung M (2000) Eavesdropping games: a graph-theoretic approach to privacy in distributed systems. J ACM 47:225\u2013243","journal-title":"J ACM"},{"key":"9042_CR14","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jctb.2000.2031","volume":"82","author":"T Johnson","year":"2001","unstructured":"Johnson T, Robertson N, Seymour P, Thomas R (2001) Directed tree-width. J Comb Theor Ser B 82:138\u2013154","journal-title":"J Comb Theor Ser B"},{"key":"9042_CR15","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L Kirousis","year":"1996","unstructured":"Kirousis L, Papadimitriou C (1996) Searching and pebbling. Theor Comput Sci 47:205\u2013218","journal-title":"Theor Comput Sci"},{"key":"9042_CR16","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A LaPaugh","year":"1993","unstructured":"LaPaugh A (1993) Recontamination does not help to search a graph. J ACM 40:224\u2013245","journal-title":"J ACM"},{"key":"9042_CR17","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N Megiddo","year":"1998","unstructured":"Megiddo N, Hakimi S, Garey M Johnson D, Papadimitriou C (1998) The complexity of searching a graph. J ACM 35:18\u201344","journal-title":"J ACM"},{"key":"9042_CR18","doi-asserted-by":"crossref","unstructured":"Obdr\u017e\u00e1lek (2006) DAG-width: connectivity measure for directed graphs. In: Proceedings of the 17th annual ACM-SIAM symposium on discrete algorithm (SODA), pp 814\u2013821","DOI":"10.1145\/1109557.1109647"},{"key":"9042_CR19","series-title":"Lecture notes in Mathematics","first-page":"426","volume-title":"Theory and applications of graphs","author":"T Parsons","year":"1976","unstructured":"Parsons T (1976) Pursuit-evasion in a graph. In: Theory and applications of graphs. Lecture notes in Mathematics. Springer, Berlin, pp 426\u2013441"},{"key":"9042_CR20","unstructured":"Yang B, Cao Y (2006) Monotonicity of digraph directed searching (submitted)"},{"key":"9042_CR21","unstructured":"Yang B, Cao Y (2006) Digraph searching, directed vertex separation and directed pathwidth (submitted)"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9042-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9042-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9042-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:11Z","timestamp":1559261891000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9042-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3,21]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,9,27]]}},"alternative-id":["9042"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9042-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,3,21]]}}}