{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,16]],"date-time":"2024-09-16T10:16:23Z","timestamp":1726481783383},"reference-count":55,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2016,10,1]],"date-time":"2016-10-01T00:00:00Z","timestamp":1475280000000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2012,10]]},"DOI":"10.1016\/j.ic.2012.08.004","type":"journal-article","created":{"date-parts":[[2012,9,12]],"date-time":"2012-09-12T00:38:56Z","timestamp":1347410336000},"page":"1-16","source":"Crossref","is-referenced-by-count":29,"special_numbering":"C","title":["Connected graph searching"],"prefix":"10.1016","volume":"219","author":[{"given":"Lali","family":"Barri\u00e8re","sequence":"first","affiliation":[]},{"given":"Paola","family":"Flocchini","sequence":"additional","affiliation":[]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[]},{"given":"Nicolas","family":"Nisse","sequence":"additional","affiliation":[]},{"given":"Nicola","family":"Santoro","sequence":"additional","affiliation":[]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2012.08.004_br0010","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander graphs and their applications","volume":"43","author":"Hoory","year":"2006","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"key":"10.1016\/j.ic.2012.08.004_br0020","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1111\/1467-8659.t01-1-00649","article-title":"On the optimality of valence-based connectivity coding","volume":"22","author":"Gotsman","year":"2003","journal-title":"Comput. Graph. Forum"},{"key":"10.1016\/j.ic.2012.08.004_br0030","series-title":"Proc. of the 14th IEEE Visualization (VIS 2003)","first-page":"61","article-title":"Large mesh simplification using processing sequences","author":"Isenburg","year":"2003"},{"key":"10.1016\/j.ic.2012.08.004_br0040","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/367211.367250","article-title":"An agent-based approach for building complex software systems","volume":"44","author":"Jennings","year":"2001","journal-title":"Commun. ACM"},{"key":"10.1016\/j.ic.2012.08.004_br0050","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","article-title":"The complexity of searching a graph","volume":"35","author":"Megiddo","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ic.2012.08.004_br0060","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","article-title":"An annotated bibliography on guaranteed graph searching","volume":"399","author":"Fomin","year":"2008","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0070","series-title":"Computational Graph Theory","first-page":"17","article-title":"Graph problems related to gate matrix layout and PLA folding","volume":"vol. 7","author":"M\u00f6hring","year":"1990"},{"key":"10.1016\/j.ic.2012.08.004_br0080","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","article-title":"Searching and pebbling","volume":"47","author":"Kirousis","year":"1986","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0090","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/333979.333980","article-title":"Eavesdropping games: a graph-theoretic approach to privacy in distributed systems","volume":"47","author":"Franklin","year":"2000","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ic.2012.08.004_br0100","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1568318.1568320","article-title":"Generalized hypertree decompositions: NP-hardness and tractable variants","volume":"56","author":"Gottlob","year":"2009","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ic.2012.08.004_br0110","series-title":"Theory and Applications of Graphs, Proc. Internat. Conf., Western Mich. Univ.","first-page":"426","article-title":"Pursuit-evasion in a graph","volume":"vol. 642","author":"Parsons","year":"1978"},{"key":"10.1016\/j.ic.2012.08.004_br0120","series-title":"Proc. of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic Univ.","first-page":"549","article-title":"The search number of a connected graph","volume":"vol. XXI","author":"Parsons","year":"1978"},{"key":"10.1016\/j.ic.2012.08.004_br0130","first-page":"1345","article-title":"A problem of pursuit in the absence of information on the pursued","volume":"18","author":"Petrov","year":"1982","journal-title":"Differ. Uravn."},{"key":"10.1016\/j.ic.2012.08.004_br0140","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","article-title":"Interval graphs and searching","volume":"55","author":"Kirousis","year":"1985","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2012.08.004_br0150","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/j.jctb.2004.08.001","article-title":"Graph minors. XX. Wagner\u02bcs conjecture","volume":"92","author":"Robertson","year":"2004","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ic.2012.08.004_br0160","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","article-title":"Monotonicity in graph searching","volume":"12","author":"Bienstock","year":"1991","journal-title":"J. Algorithms"},{"key":"10.1016\/j.ic.2012.08.004_br0170","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1145\/151261.151263","article-title":"Recontamination does not help to search a graph","volume":"40","author":"LaPaugh","year":"1993","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ic.2012.08.004_br0180","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/S0166-218X(02)00459-6","article-title":"On the monotonicity of games generated by symmetric submodular functions","volume":"131","author":"Fomin","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2012.08.004_br0190","doi-asserted-by":"crossref","first-page":"5770","DOI":"10.1016\/j.disc.2008.05.033","article-title":"Sweeping graphs with large clique number","volume":"309","author":"Yang","year":"2009","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2012.08.004_br0200","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1995.1009","article-title":"Approximating treewidth, pathwidth, frontsize, and shortest elimination tree","volume":"18","author":"Bodlaender","year":"1995","journal-title":"J. Algorithms"},{"key":"10.1016\/j.ic.2012.08.004_br0210","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/s00453-007-9041-6","article-title":"Nondeterministic graph searching: from pathwidth to treewidth","volume":"53","author":"Fomin","year":"2009","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2012.08.004_br0220","doi-asserted-by":"crossref","unstructured":"H.L. Bodlaender, D.M. Thilikos, Computing small search numbers in linear time, in: Proc. First International Workshop on Parameterized and Exact Computation (IWPEC 2004), Bergen, Norway, pp. 37\u201348.","DOI":"10.1007\/978-3-540-28639-4_4"},{"key":"10.1016\/j.ic.2012.08.004_br0230","doi-asserted-by":"crossref","first-page":"727","DOI":"10.1145\/44483.44491","article-title":"Nonconstructive tools for proving polynomial-time decidability","volume":"35","author":"Fellows","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/j.ic.2012.08.004_br0240","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1006\/jctb.1995.1006","article-title":"Graph minors. XIII. The disjoint paths problem","volume":"63","author":"Robertson","year":"1995","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ic.2012.08.004_br0250","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","article-title":"Graph minors. X. Obstructions to tree-decomposition","volume":"52","author":"Robertson","year":"1991","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.ic.2012.08.004_br0260","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1130\/0016-7606(1945)56[275:EDOSAT]2.0.CO;2","article-title":"Erosional development of streams and their drainage basins: hydro-physical approach to quantitative morphology","volume":"56","author":"Horton","year":"1945","journal-title":"Geol. Soc. Am. Bull."},{"key":"10.1016\/j.ic.2012.08.004_br0270","doi-asserted-by":"crossref","first-page":"1117","DOI":"10.1130\/0016-7606(1952)63[1117:HAAOET]2.0.CO;2","article-title":"Hypsometric (area-altitude) analysis of erosional topology","volume":"63","author":"Strahler","year":"1952","journal-title":"Geol. Soc. Am. Bull."},{"key":"10.1016\/j.ic.2012.08.004_br0280","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1029\/TR038i006p00913","article-title":"Quantitative analysis of watershed geomorphology","volume":"8","author":"Strahler","year":"1957","journal-title":"Trans. Am. Geophys. Union"},{"key":"10.1016\/j.ic.2012.08.004_br0290","doi-asserted-by":"crossref","first-page":"937","DOI":"10.1111\/j.1752-1688.2004.tb01057.x","article-title":"A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks","volume":"40","author":"Gleyzer","year":"2004","journal-title":"J. Am. Water Resour. Assoc."},{"key":"10.1016\/j.ic.2012.08.004_br0300","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0304-3975(79)90009-4","article-title":"The number of registers required for evaluating arithmetic expressions","volume":"9","author":"Flajolet","year":"1979","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0310","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1086\/337238","article-title":"Bifurcation ratios and the adaptive geometry of trees","volume":"142","author":"Borchert","year":"1981","journal-title":"Botanical Gazette"},{"key":"10.1016\/j.ic.2012.08.004_br0320","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/BF02459562","article-title":"Some mathematical properties of branching trees with application to the respiratory system","volume":"38","author":"Horsfield","year":"1976","journal-title":"Bull. Math. Biol."},{"key":"10.1016\/j.ic.2012.08.004_br0330","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1140\/epjb\/e2004-00130-1","article-title":"Community analysis in social networks","volume":"38","author":"Arenas","year":"2004","journal-title":"Eur. Phys. J. B"},{"key":"10.1016\/j.ic.2012.08.004_br0340","first-page":"72","article-title":"An intuitive approach to speleotopology","volume":"VI","author":"Breisch","year":"1967","journal-title":"Southwestern Cavers"},{"key":"10.1016\/j.ic.2012.08.004_br0350","series-title":"Proc. of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2002)","first-page":"200","article-title":"Capture of an intruder by mobile agents","author":"Barri\u00e8re","year":"2002"},{"key":"10.1016\/j.ic.2012.08.004_br0360","series-title":"Proc. of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003)","first-page":"34","article-title":"Searching is not jumping","volume":"vol. 2880","author":"Barri\u00e8re","year":"2003"},{"key":"10.1016\/j.ic.2012.08.004_br0370","series-title":"7th International Colloquium on Graph Theory","first-page":"213","article-title":"Connected graph searching in outerplanar graphs","volume":"vol. 22","author":"Fomin","year":"2005"},{"key":"10.1016\/j.ic.2012.08.004_br0380","series-title":"Proc. of the 7th Latin American Symposium on Theoretical Informatics (LATIN 2006)","first-page":"479","article-title":"Connected treewidth and connected graph searching","volume":"vol. 3887","author":"Fraigniaud","year":"2006"},{"key":"10.1016\/j.ic.2012.08.004_br0390","doi-asserted-by":"crossref","first-page":"2603","DOI":"10.1016\/j.dam.2008.08.007","article-title":"Connected graph searching in chordal graphs","volume":"157","author":"Nisse","year":"2009","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2012.08.004_br0400","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1142\/S0218195906002038","article-title":"Boundary-optimal triangulation flooding","volume":"16","author":"Nowakowski","year":"2006","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"10.1016\/j.ic.2012.08.004_br0410","doi-asserted-by":"crossref","first-page":"1383","DOI":"10.1016\/j.ic.2008.09.002","article-title":"Monotony properties of connected visible graph searching","volume":"206","author":"Fraigniaud","year":"2008","journal-title":"Inform. and Comput."},{"key":"10.1016\/j.ic.2012.08.004_br0420","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.tcs.2008.02.004","article-title":"Distributed chasing of network intruders","volume":"399","author":"Blin","year":"2008","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0430","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1142\/S0129054107004838","article-title":"Decontamination of chordal rings and tori using mobile agents","volume":"18","author":"Flocchini","year":"2007","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0440","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1002\/net.20240","article-title":"Decontamination of hypercubes by mobile agents","volume":"52","author":"Flocchini","year":"2008","journal-title":"Networks"},{"key":"10.1016\/j.ic.2012.08.004_br0450","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/s00446-009-0089-1","article-title":"The cost of monotonicity in distributed graph searching","volume":"22","author":"Ilcinkas","year":"2009","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.ic.2012.08.004_br0460","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1016\/j.tcs.2008.08.020","article-title":"Graph searching with advice","volume":"410","author":"Nisse","year":"2009","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2012.08.004_br0470","series-title":"Reliability of Computer and Communication Networks","first-page":"33","article-title":"Graph searching, path-width, tree-width and related problems (a survey)","volume":"vol. 5","author":"Bienstock","year":"1991"},{"key":"10.1016\/j.ic.2012.08.004_br0480","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF01215352","article-title":"Call routing and the ratcatcher","volume":"14","author":"Seymour","year":"1994","journal-title":"Combinatorica"},{"key":"10.1016\/j.ic.2012.08.004_br0490","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF02785579","article-title":"On embedding trees into uniformly convex Banach spaces","volume":"114","author":"Matou\u0161ek","year":"1999","journal-title":"Israel J. Math."},{"key":"10.1016\/j.ic.2012.08.004_br0500","series-title":"Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC 1998)","first-page":"169","article-title":"Trees and Euclidean metrics","author":"Linial","year":"1999"},{"key":"10.1016\/j.ic.2012.08.004_br0510","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0012-365X(94)90092-2","article-title":"Minimal acyclic forbidden minors for the family of graphs with bounded path-width","volume":"127","author":"Takahashi","year":"1994","journal-title":"Discrete Math."},{"key":"10.1016\/j.ic.2012.08.004_br0520","unstructured":"F. Huc, Conception de R\u00e9seaux Dynamiques Tol\u00e9rants aux Pannes, PhD thesis, Nice Sophia Antipolis, Projet MASCOTTE (CNRS-UNSA) INRIA, 2008."},{"key":"10.1016\/j.ic.2012.08.004_br0530","doi-asserted-by":"crossref","unstructured":"R. Mihai, I. Todinca, Pathwidth is NP-hard for weighted trees, in: Frontiers in Algorithmics, 2009, pp. 181\u2013195.","DOI":"10.1007\/978-3-642-02270-8_20"},{"key":"10.1016\/j.ic.2012.08.004_br0540","series-title":"28th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs","first-page":"416","article-title":"From pathwidth to connected pathwidth","author":"Dereniowski","year":"2011"},{"key":"10.1016\/j.ic.2012.08.004_br0550","doi-asserted-by":"crossref","first-page":"5700","DOI":"10.1016\/j.tcs.2011.06.017","article-title":"Connected searching of weighted trees","volume":"412","author":"Dereniowski","year":"2011","journal-title":"Theoret. Comput. Sci."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540112001277?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540112001277?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,11,20]],"date-time":"2018-11-20T17:20:39Z","timestamp":1542734439000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540112001277"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":55,"alternative-id":["S0890540112001277"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2012.08.004","relation":{},"ISSN":["0890-5401"],"issn-type":[{"type":"print","value":"0890-5401"}],"subject":[],"published":{"date-parts":[[2012,10]]}}}