{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:32Z","timestamp":1760202632908},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,5,7]],"date-time":"2011-05-07T00:00:00Z","timestamp":1304726400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9524-3","type":"journal-article","created":{"date-parts":[[2011,5,6]],"date-time":"2011-05-06T11:56:49Z","timestamp":1304683009000},"page":"158-190","source":"Crossref","is-referenced-by-count":7,"title":["A Distributed Algorithm for Computing the Node Search Number in Trees"],"prefix":"10.1007","volume":"63","author":[{"given":"David","family":"Coudert","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Huc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dorian","family":"Mazauric","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,5,7]]},"reference":[{"key":"9524_CR1","first-page":"200","volume-title":"14th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"L. Barri\u00e8re","year":"2002","unstructured":"Barri\u00e8re, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Capture of an intruder by mobile agents. In: 14th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), San Diego, California, USA (part of FCRC 2003), June 2002, pp. 200\u2013209. ACM, New York (2002)"},{"key":"9524_CR2","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":"29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"L. Barri\u00e8re","year":"2003","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Santoro, N., Thilikos, D.M.: Searching is not jumping. In: Bodlaender, H.L. (ed.) 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Elspeet, The Netherlands, June 2003. Lecture Notes in Computer Science, vol. 2880, pp. 34\u201345. Springer, Berlin (2003)"},{"issue":"5","key":"9524_CR3","first-page":"72","volume":"VI","author":"R.L. Breisch","year":"1967","unstructured":"Breisch, R.L.: An intuitive approach to speleotopology. Southwest. Cavers VI(5), 72\u201378 (1967)","journal-title":"Southwest. Cavers"},{"key":"9524_CR4","first-page":"1","volume-title":"13th Conference on Optical Network Design and Modeling (ONDM)","author":"D. Coudert","year":"2009","unstructured":"Coudert, D., Huc, F., Mazauric, D., Nisse, N., Sereni, J.-S.: Reconfiguration of the routing in WDM networks with two classes of services. In: 13th Conference on Optical Network Design and Modeling (ONDM), Braunschweig, Germany, February 2009, pp. 1\u20136. IEEE, Los Alamitos (2009)"},{"key":"9524_CR5","first-page":"17","volume-title":"7\u00e8mes Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications (AlgoTel\u201905)","author":"D. Coudert","year":"2005","unstructured":"Coudert, D., Perennes, S., Pham, Q.-C., Sereni, J.-S.: Rerouting requests in WDM networks. In: 7\u00e8mes Rencontres Francophones sur les Aspects Algorithmiques des T\u00e9l\u00e9communications (AlgoTel\u201905), Presqu\u2019\u00eele de Giens, France, May 2005, pp. 17\u201320 (2005)"},{"key":"9524_CR6","doi-asserted-by":"crossref","first-page":"1094","DOI":"10.1016\/j.dam.2011.03.010","volume":"159","author":"D. Coudert","year":"2011","unstructured":"Coudert, D., Sereni, J.-S.: Characterization of graphs and digraphs with small process number. Discrete Appl. Math. 159, 1094\u20131109 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"9524_CR7","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1145\/568522.568523","volume":"34","author":"J. D\u00edaz","year":"2002","unstructured":"D\u00edaz, J., Petit, J., Serna, M.: A survey on graph layout problems. ACM Comput. Surv. 34(3), 313\u2013356 (2002)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"9524_CR8","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"Ellis, J.A., Sudborough, I.H., Turner, J.S.: The vertex separation and search number of a graph. Inf. Comput. 113(1), 50\u201379 (1994)","journal-title":"Inf. Comput."},{"issue":"3","key":"9524_CR9","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/s00453-007-9041-6","volume":"53","author":"F.V. Fomin","year":"2009","unstructured":"Fomin, F.V., Fraigniaud, P., Nisse, N.: Nondeterministic graph searching: from pathwidth to treewidth. Algorithmica 53(3), 358\u2013373 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"9524_CR10","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.02.040","volume":"399","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3), 236\u2013245 (2008)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9524_CR11","first-page":"88","volume":"24","author":"P.A. Golovach","year":"1991","unstructured":"Golovach, P.A.: Search number, node search number, and vertex separator of a graph. Vestn. Leningr. Univ., Math. 24(1), 88\u201390 (1991)","journal-title":"Vestn. Leningr. Univ., Math."},{"issue":"6","key":"9524_CR12","doi-asserted-by":"crossref","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 pathwidth. Inf. Process. Lett. 42(6), 345\u2013350 (1992). doi: 10.1016\/0020-0190(92)90234-M","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9524_CR13","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"M. Kirousis","year":"1986","unstructured":"Kirousis, M., Papadimitriou, C.H.: Searching and pebbling. Theor. Comput. Sci. 47(2), 205\u2013218 (1986)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9524_CR14","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach. 40(2), 224\u2013245 (1993). doi: 10.1145\/151261.151263","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"9524_CR15","doi-asserted-by":"crossref","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. J. Assoc. Comput. Mach. 35(1), 18\u201344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9524_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-642-02270-8_20","volume-title":"3rd International Workshop on Frontiers in Algorithmics (FAW)","author":"R. Mihai","year":"2009","unstructured":"Mihai, R., Todinca, I.: Pathwidth is NP-hard for weighted trees. In: Deng, X., Hopcroft, J.E., Xue, J. (eds.) 3rd International Workshop on Frontiers in Algorithmics (FAW), Hefei, China, June 2009, Lecture Notes in Computer Science, vol. 5598, pp. 181\u2013195. Springer, Berlin (2009)"},{"key":"9524_CR17","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BFb0070400","volume-title":"Theory and Applications of Graphs","author":"T.D. Parsons","year":"1978","unstructured":"Parsons, T.D.: Pursuit-evasion in a graph. In: Theory and Applications of Graphs. Lecture Notes in Mathematics, vol. 642, pp. 426\u2013441. Springer, Berlin (1978)"},{"issue":"2","key":"9524_CR18","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/S0304-3975(99)00241-8","volume":"240","author":"S.-L. Peng","year":"2000","unstructured":"Peng, S.-L., Hob, C.-W., Hsu, T.-S., Ko, M.-T., Tanga, C.Y.: Edge and node searching problems on trees. Theor. Comput. Sci. 240(2), 429\u2013446 (2000)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9524_CR19","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. I. Excluding a forest. J. Comb. Theory, Ser. B 35(1), 39\u201361 (1983)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9524_CR20","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/978-3-642-46908-4_70","volume-title":"Topics in Combinatorics and Graph Theory","author":"P. Scheffler","year":"1990","unstructured":"Scheffler, P.: A linear algorithm for the pathwidth of trees. In: R.\u00a0Bodendiek, R.H. (ed.) Topics in Combinatorics and Graph Theory, pp. 613\u2013620. Physica-Verlag, Heidelberg (1990)"},{"issue":"1","key":"9524_CR21","doi-asserted-by":"crossref","first-page":"40","DOI":"10.1016\/S0196-6774(02)00225-0","volume":"47","author":"K. Skodinis","year":"2003","unstructured":"Skodinis, K.: Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time. J. Algorithms 47(1), 40\u201359 (2003)","journal-title":"J. Algorithms"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9524-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9524-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9524-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9524-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,7]]},"references-count":21,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9524"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9524-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,7]]}}}