{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T11:56:20Z","timestamp":1742385380315},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540620488"},{"type":"electronic","value":"9783540496335"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/bfb0009491","type":"book-chapter","created":{"date-parts":[[2005,10,20]],"date-time":"2005-10-20T14:32:17Z","timestamp":1129818737000},"page":"156-165","source":"Crossref","is-referenced-by-count":4,"title":["Graph searching on chordal graphs"],"prefix":"10.1007","author":[{"given":"Sheng-Lung","family":"Peng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming-Tat","family":"Ko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chin-Wen","family":"Ho","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tsan-sheng","family":"Hsu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chuan-Yi","family":"Tang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,10,11]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","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), pp. 277\u2013284.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"16_CR2","first-page":"114","volume":"700","author":"H.L. Bodlaender","year":"1993","unstructured":"H.L. BODLAENDER, T. KLOKS, and D. KRATSCH, Treewidth and pathwidth of permutation graphs, 20th ICALP, LNCS 700(1993), pp. 114\u2013125.","journal-title":"20th ICALP, LNCS"},{"key":"16_CR3","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. MOHRING, The pathwidth and treewidth of cographs, SIAM J. Disc. Math., 6(1993), pp. 181\u2013188.","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR4","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), pp. 239\u2013245.","journal-title":"J. Algorithms"},{"key":"16_CR5","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F. Gavril","year":"1974","unstructured":"F. GAVRIL, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory Ser. B, 16(1974), pp.47\u201356.","journal-title":"J. Comb. Theory Ser. B"},{"key":"16_CR6","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, Discr. Appl. Math. 45(1993), pp. 233\u2013248.","journal-title":"Discr. Appl. Math."},{"key":"16_CR7","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. Letter, 42(1992), pp. 345\u2013350.","journal-title":"Inform. Process. Letter"},{"key":"16_CR8","volume-title":"Ph.D. Thesis","author":"T. Kloks","year":"1993","unstructured":"T. KLOKS, Treewidth, Ph.D. Thesis, Utrecht University, The Netherlands, 1993."},{"key":"16_CR9","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), pp. 181\u2013184.","journal-title":"Disc. Math."},{"key":"16_CR10","doi-asserted-by":"crossref","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 Comp. Scie. 47(1986), pp. 205\u2013218.","journal-title":"Theoretical Comp. Scie."},{"key":"16_CR11","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), pp. 87\u201392.","journal-title":"Disc. Appl. Math."},{"key":"16_CR12","doi-asserted-by":"crossref","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. of the Assoc. Comput. Mach., 40(1993), pp. 224\u2013245.","journal-title":"J. of the Assoc. Comput. Mach."},{"key":"16_CR13","doi-asserted-by":"crossref","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. of the Assoc. Comput. Mach., 35(1988), pp. 18\u201344.","journal-title":"J. of the Assoc. Comput. Mach."},{"key":"16_CR14","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-7091-9076-0_2","volume-title":"Computational Graph Theory","author":"R.H. Mohring","year":"1990","unstructured":"R.H. MOHRING, Graph problems related to gate matrix layout and PLA folding, in: G. TINNHOFER et al., eds., Computational Graph Theory (Springer, Wien, 1990), pp. 17\u201332."},{"key":"16_CR15","doi-asserted-by":"crossref","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 \u2014 complete for edge weighted trees, Theoretical Comp. Scie. 58(1988), pp. 209\u2013229.","journal-title":"Theoretical Comp. Scie."},{"key":"16_CR16","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, pp. 426\u2013441."},{"key":"16_CR17","doi-asserted-by":"crossref","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), pp. 39\u201361.","journal-title":"J. Comb. Theory Ser. B"},{"key":"16_CR18","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":"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), pp. 613\u2013620."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0009491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,4]],"date-time":"2019-02-04T01:26:47Z","timestamp":1549243607000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0009491"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540620488","9783540496335"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/bfb0009491","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}