{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T14:57:16Z","timestamp":1786978636157,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648246","type":"print"},{"value":"9783540685357","type":"electronic"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68535-9_32","type":"book-chapter","created":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T04:31:22Z","timestamp":1193459482000},"page":"279-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["A Linear-Time Algorithm for Constructing an Optimal Node-Search Strategy of a Tree"],"prefix":"10.1007","author":[{"given":"Sheng-Lung","family":"Peng","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chin-Wen","family":"Ho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tsan-sheng","family":"Hsu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming-Tat","family":"Ko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chuan Yi","family":"Tang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2002,6,4]]},"reference":[{"key":"32_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D.G. Corneil, and A. Proskurowski, Complexity of finding embeddings in a k-tree, SIAM J. Alg. Disc. Meth., 8(1987), 277\u2013284.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"D. Bienstock, Graph searching, path-width, tree-width and related problems (a survey), in: F. Roberts, F. Hwang and C. Monma, eds., Reliability of Computer and Communication Networks, DIMACS series in Disc. Math. and Theoretical Comp. Scie., Vol 5, American Math. Society, 1991, 33\u201349.","DOI":"10.1090\/dimacs\/005\/02"},{"key":"32_CR3","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0196-6774(91)90003-H","volume":"12","author":"D. Bienstock","year":"1991","unstructured":"D. Bienstock and P. Seymour, Monotonicity in graph searching, J. Algorithms, 12(1991), 239\u2013245.","journal-title":"J. Algorithms"},{"key":"32_CR4","series-title":"Technical Report","volume-title":"A partial k-arboretum of graphs with bounded treewidth","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Technical Report UU-CS-1996-02, Department of Computer Science, Utrecht University, Utrecht, the Netherlands, 1996."},{"key":"32_CR5","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H.L. Bodlaender","year":"1996","unstructured":"H.L. Bodlaender and T. Kloks, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, J. Algorithms, 21(1996), 358\u2013402.","journal-title":"J. Algorithms"},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H.L. Bodlaender","year":"1995","unstructured":"H.L. Bodlaender, T. Kloks, and D. Kratsch, Treewidth and pathwidth of permutation graphs, SIAM J. Disc. Math., 8(1995), 606\u2013616.","journal-title":"SIAM J. Disc. Math."},{"key":"32_CR7","series-title":"Technical Report","volume-title":"Treewidth and minimum fill-in on d-trapezoid graphs","author":"H.L. Bodlaender","year":"1995","unstructured":"H.L. Bodlaender, T. Kloks, D. Kratsch, and H. Muller, Treewidth and minimum fill-in on d-trapezoid graphs, Technical Report UU-CS-1995-34, Department of Computer Science, Utrecht University, Utrecht, the Netherlands, 1995."},{"key":"32_CR8","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H.L. Bodlaender","year":"1993","unstructured":"H.L. Bodlaender and R.H. M\u00f6hring, The pathwidth and treewidth of cographs, SIAM J. Disc. Math., 6(1993), 181\u2013188.","journal-title":"SIAM J. Disc. Math."},{"key":"32_CR9","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J.A. Ellis","year":"1994","unstructured":"J.A. Ellis, I.H. Sudborough, and J.S. Turner, The vertexsepa ration and search number of a graph, Information and Computation, 113(1994), 50\u201379.","journal-title":"Information and Computation"},{"key":"32_CR10","volume-title":"Nonlinear and Game-Theoretic Control Synthesis","author":"F.V. Fomin","year":"1995","unstructured":"F.V. Fomin and N.N. Petrov, Pursuit-evasion and search problems on graphs, In Nonlinear and Game-Theoretic Control Synthesis, Euler Int. Math. Institute, St. Petersburg, 13\u201326 March, 1995, Update May 1996."},{"key":"32_CR11","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0166-218X(93)90012-D","volume":"45","author":"J. Gustedt","year":"1993","unstructured":"J. Gustedt, On the pathwidth of chordal graphs, Disc. Appl. Math., 45(1993), 233\u2013248.","journal-title":"Disc. Appl. Math."},{"key":"32_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":"N.G. Kinnersley, The vertex separation number of a graph equals its path-width, Inform. Process. Lett., 42(1992), 345\u2013350.","journal-title":"Inform. Process. Lett."},{"key":"32_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth, Computations and Applications","author":"T. Kloks","year":"1994","unstructured":"T. Kloks, Treewidth, Computations and Applications, LNCS 842, Springer, 1994."},{"key":"32_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-57273-2_61","volume-title":"ESA\u201993","author":"T. Kloks","year":"1993","unstructured":"T. Kloks, H. Bodlaender, H. Muller, and D. Kratsch, Computing treewidth and minimum fill-in: all you need are the minimal separators, ESA\u201993, LNCS 726, 260\u2013271, 1993. Erratum: ESA\u201994, LNCS 855, pp. 508, 1994."},{"key":"32_CR15","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L.M. Kirousis","year":"1985","unstructured":"L.M. Kirousis and C.H. Papadimitriou, Interval graph and searching, Disc. Math., 55(1985), 181\u2013184.","journal-title":"Disc. Math."},{"key":"32_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L.M. Kirousis","year":"1986","unstructured":"L.M. Kirousis and C.H. Papadimitriou, Searching and pebbling, Theoretical Comput. Scie., 47(1986), 205\u2013218.","journal-title":"Theoretical Comput. Scie."},{"key":"32_CR17","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0166-218X(92)90208-R","volume":"36","author":"A. Kornai","year":"1992","unstructured":"A. Kornai and Z. Tuza, Narrowness, pathwidth, and their application in natural language processing, Disc. Appl. Math., 36(1992), 87\u201392.","journal-title":"Disc. Appl. Math."},{"key":"32_CR18","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1145\/151261.151263","volume":"40","author":"A.S. LaPaugh","year":"1993","unstructured":"A.S. LaPaugh, Recontamination does not help to search a graph, J. Assoc. Comput. Mach., 40(1993), 224\u2013245.","journal-title":"J. Assoc. Comput. Mach."},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, S.L. Hakimi, M.R. Garey, D.S. Johnson, and C.H. Papadimitriou, The complexity of searching a graph, J. Assoc. Comput. Mach., 35(1988), 18\u201344.","journal-title":"J. Assoc. Comput. Mach."},{"key":"32_CR20","doi-asserted-by":"crossref","unstructured":"R.H. M\u00f6hring, Graph problems related to gate matrix layout and PLA folding, in: G. Tinnhofer et al., eds., Computational Graph Theory, Springer, 1990, 17\u201332.","DOI":"10.1007\/978-3-7091-9076-0_2"},{"key":"32_CR21","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"B. Monien and I.H. Sudborough, Min cut is NP-complete for edge weighted trees, Theoretical Comput. Sci., 58(1988), 209\u2013229.","journal-title":"Theoretical Comput. Sci."},{"key":"32_CR22","first-page":"426","volume-title":"Theory and applications of graphs","author":"T.D. Parsons","year":"1976","unstructured":"T.D. Parsons, Pursuit-evasion in a graph, in Y. Alavi and D.R. Lick, eds., Theory and applications of graphs, Springer-Verlag, New York, 1976, 426\u2013441."},{"key":"32_CR23","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/BFb0045095","volume-title":"COCOON\u201997","author":"S.L. Peng","year":"1997","unstructured":"S.L. Peng, C.W. Ho, T.-s. Hsu, M.T. Ko, and C.Y. Tang, Edge and node searching problems on trees, COCOON\u201997, LNCS 1276, 284\u2013293, 1997."},{"key":"32_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1007\/BFb0009491","volume-title":"ISAAC\u201996","author":"S.L. Peng","year":"1996","unstructured":"S.L. Peng, M.T. Ko, C.W. Ho, T.-s. Hsu, and C.Y. Tang, Graph searching on chordal graphs, ISAAC\u201996, LNCS 1178, 156\u2013165, 1996."},{"key":"32_CR25","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"N. Robertson and P.D. Seymour, Graph minors I. Excluding a forest, J. Comb. Theory Ser. B, 35(1983), 39\u201361.","journal-title":"J. Comb. Theory Ser. B"},{"key":"32_CR26","doi-asserted-by":"publisher","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":"P. Scheffler, A linear algorithm for the pathwidth of trees, in: R. Bodendiek and R. Henn, eds., Topics in Combinatorics and Graph Theory (Physica-Verlag, Heidelberg, 1990), 613\u2013620."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68535-9_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,19]],"date-time":"2020-05-19T05:55:45Z","timestamp":1589867745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68535-9_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648246","9783540685357"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-68535-9_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"4 June 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}