{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:57:02Z","timestamp":1725566222621},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_4","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"37-48","source":"Crossref","is-referenced-by-count":12,"title":["Computing Small Search Numbers in Linear Time"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dimitrios M.","family":"Thilikos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"4_CR1","series-title":"DIMACS Ser. Discrete Math. Theoret. Comput. Sci.","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1090\/dimacs\/005\/02","volume-title":"Reliability of computer and communication networks (New Brunswick, NJ, 1989)","author":"D. Bienstock","year":"1991","unstructured":"Bienstock, D.: Graph searching, path-width, tree-width and related problems (a survey). In: Reliability of computer and communication networks (New Brunswick, NJ, 1989). DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol.\u00a05, pp. 33\u201349. Amer. Math. Soc., Providence (1991)"},{"issue":"2","key":"4_CR2","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(2), 239\u2013245 (1991)","journal-title":"Journal of Algorithms"},{"issue":"6","key":"4_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput.\u00a025(6), 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"4_CR4","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"Bodlaender, H.L., Kloks, T.: Efficient and constructive algorithms for the pathwidth and treewidth of graphs. Journal of Algorithms\u00a021, 358\u2013402 (1996)","journal-title":"Journal of Algorithms"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/3-540-63165-8_217","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1997","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Constructive linear time algorithms for branchwidth. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 627\u2013637. Springer, Heidelberg (1997)"},{"key":"4_CR6","unstructured":"Bodlaender, H.L., Thilikos, D.M.: Computing small search numbers in linear time. Technical Report UU-CS-1998-05, Dept. of Computer Science, Utrecht University (1998)"},{"key":"4_CR7","first-page":"72","volume":"VI","author":"R. Breisch","year":"1967","unstructured":"Breisch, R.: An intuitive approach to speleotopology. A publication of the Southwestern Region of the National Speleological Society\u00a0VI, 72\u201378 (1967)","journal-title":"A publication of the Southwestern Region of the National Speleological Society"},{"key":"4_CR8","doi-asserted-by":"publisher","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.: Fugitive-search games on graphs and related parameters. Theoretical Computer Science\u00a0172, 233\u2013254 (1997)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","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. Inform. and Comput.\u00a0113(1), 50\u201379 (1994)","journal-title":"Inform. and Comput."},{"issue":"3","key":"4_CR10","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M.R. Fellows","year":"1994","unstructured":"Fellows, M.R., Langston, M.A.: On search, decision, and the efficiency of polynomial-time algorithms. J. Comput. System Sci.\u00a049(3), 769\u2013779 (1994)","journal-title":"J. Comput. System Sci."},{"key":"4_CR11","series-title":"Contemp. Math.","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1090\/conm\/065\/891251","volume-title":"Logic and combinatorics (Arcata, Calif., 1985)","author":"H. Friedman","year":"1987","unstructured":"Friedman, H., Robertson, N., Seymour, P.: The metamathematics of the graph minor theorem. In: Logic and combinatorics (Arcata, Calif., 1985). Contemp. Math., vol.\u00a065, pp. 229\u2013261. Amer. Math. Soc., Providence (1987)"},{"issue":"6","key":"4_CR12","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.: he vertex separation number of a graph equals its path-width. Inform. Process. Lett.\u00a042(6), 345\u2013350 (1992)","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"4_CR13","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L.M. Kirousis","year":"1985","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Interval graphs and searching. Discrete Math.\u00a055(2), 181\u2013184 (1985)","journal-title":"Discrete Math."},{"issue":"2","key":"4_CR14","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L.M. Kirousis","year":"1986","unstructured":"Kirousis, L.M., Papadimitriou, C.H.: Searching and pebbling. Theoret. Comput. Sci.\u00a047(2), 205\u2013218 (1986)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"4_CR15","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.\u00a040(2), 224\u2013245 (1993)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"1","key":"4_CR16","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.\u00a035(1), 18\u201344 (1988)","journal-title":"J. Assoc. Comput. Mach."},{"key":"4_CR17","series-title":"Comput. Suppl.","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-7091-9076-0_2","volume-title":"Computational graph theory","author":"R.H. M\u00f6hring","year":"1990","unstructured":"M\u00f6hring, R.H.: Graph problems related to gate matrix layout and PLA folding. In: Computational graph theory. Comput. Suppl., vol.\u00a07, pp. 17\u201351. Springer, Vienna (1990)"},{"key":"4_CR18","series-title":"Lecture Notes in Math.","doi-asserted-by":"crossref","first-page":"426","DOI":"10.1007\/BFb0070400","volume-title":"Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976","author":"T.D. Parsons","year":"1978","unstructured":"Parsons, T.D.: Pursuit-evasion in a graph. In Theory and applications of graphs. In: AII 1992. Lecture Notes in Math., vol.\u00a0642, pp. 426\u2013441. Springer, Berlin (1978)"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Disjoint paths\u2014a survey. SIAM J. Algebraic Discrete Methods\u00a06(2), 300\u2013305 (1985)","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"4_CR20","series-title":"London Math. Soc. Lecture Note Ser.","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1017\/CBO9781107325678.009","volume-title":"Surveys in combinatorics 1985","author":"N. Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Graph minors\u2014a survey. In: Surveys in combinatorics 1985, Glasgow. London Math. Soc. Lecture Note Ser., vol.\u00a0103, pp. 153\u2013171. Cambridge Univ. Press, Cambridge (1985)"},{"key":"4_CR21","first-page":"267","volume":"9","author":"N. Robertson","year":"1990","unstructured":"Robertson, N., Seymour, P.D.: An outline of a disjoint paths algorithm. Paths, Flows and VLSI Design, Algorithms and Combinatorics\u00a09, 267\u2013292 (1990)","journal-title":"Paths, Flows and VLSI Design, Algorithms and Combinatorics"},{"issue":"1","key":"4_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. Journal of Combinatorial Theory. Series B\u00a063(1), 65\u2013110 (1995)","journal-title":"Journal of Combinatorial Theory. Series B"},{"issue":"1","key":"4_CR23","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1006\/jctb.1993.1027","volume":"58","author":"P.D. Seymour","year":"1993","unstructured":"Seymour, P.D., Thomas, R.: Graph searching and a min-max theorem for tree-width. J. Combin. Theory Ser. B\u00a058(1), 22\u201333 (1993)","journal-title":"J. Combin. Theory Ser. B"},{"key":"4_CR24","first-page":"1828","volume":"E78-A","author":"A. Takahashi","year":"1995","unstructured":"Takahashi, A., Ueno, S., Kajitani, Y.: Minimal forbidden minors for the family of graphs with proper-path-width at most two. IEICE Trans. Fundamentals\u00a0E78-A, 1828\u20131839 (1995)","journal-title":"IEICE Trans. Fundamentals"},{"key":"4_CR25","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/S0166-218X(00)00175-X","volume":"105","author":"D.M. Thilikos","year":"2000","unstructured":"Thilikos, D.M.: Algorithms and obstructions for linear-width and related search parameters. Discrete Applied Mathematics\u00a0105, 239\u2013271 (2000)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/3-540-40996-3_17","volume-title":"Algorithms and Computation","author":"D.M. Thilikos","year":"2000","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: Constructinve linear time algorithms for small cutwidth and carving-width. In: Lee, D.T., Teng, S.-H. (eds.) ISAAC 2000. LNCS, vol.\u00a01969, pp. 192\u2013203. Springer, Heidelberg (2000)"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1007\/3-540-44676-1_32","volume-title":"Algorithms - ESA 2001","author":"D.M. Thilikos","year":"2001","unstructured":"Thilikos, D.M., Serna, M.J., Bodlaender, H.L.: A polynomial time algorithm for the cutwidth of bounded degree graphs with small treewidth. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 380\u2013390. Springer, Heidelberg (2001)"},{"key":"4_CR28","unstructured":"Thomas, R.: Tree-decompositions of graphs. Lecture notes, School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia 30332, USA (1996)"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T03:30:00Z","timestamp":1620012600000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}