{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:04:01Z","timestamp":1725494641599},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540410041"},{"type":"electronic","value":"9783540452539"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45253-2_37","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T21:06:25Z","timestamp":1194987985000},"page":"403-414","source":"Crossref","is-referenced-by-count":10,"title":["Computing Optimal Linear Layouts of Trees in Linear Time"],"prefix":"10.1007","author":[{"given":"Konstantin","family":"Skodinis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,2,11]]},"reference":[{"issue":"6","key":"37_CR1","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. Bodlaender","year":"1996","unstructured":"H. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput., 25(6):1305\u20131317, 1996.","journal-title":"SIAM J. Comput."},{"key":"37_CR2","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"H. Bodlaender","year":"1996","unstructured":"H. Bodlaender and T. Kloks. Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J. Algorithms, 21:358\u2013402, 1996.","journal-title":"J. Algorithms"},{"key":"37_CR3","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H. Bodlaender","year":"1995","unstructured":"H. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidth of permutation graphs. SIAM J. Disc. Math., 8:606\u2013616, 1995.","journal-title":"SIAM J. Disc. Math."},{"key":"37_CR4","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H. Bodlaender","year":"1993","unstructured":"H. Bodlaender and R. Mohring. The pathwidth and treewidth of cographs. SIAM J. Disc. Math., 6:181\u2013188, 1993.","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"37_CR5","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1137\/0214013","volume":"14","author":"M. Chung","year":"1985","unstructured":"M. Chung, F. Makedon, I. Sudborough, and J. Turner. Polynomial algorithms for the mincut linear arrangement problem on degree restricted trees. SIAM J. Comput., 14(1): 158\u2013177, 1985.","journal-title":"SIAM J. Comput."},{"key":"37_CR6","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0022-0000(76)80048-7","volume":"13","author":"S. Cook","year":"1976","unstructured":"S. Cook and R. Sethi. Storage requirements for deterministic polynomial finite recognizable languages. J. Comput. System Sci, 13:25\u201337, 1976.","journal-title":"J. Comput. System Sci"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1006\/inco.1994.1064","volume":"113","author":"J. Ellis","year":"1994","unstructured":"J. Ellis, I. Sudborough, and J. Turner. The vertex separation and search number of a graph. Inform. Comput., 113:50\u201379, 1994.","journal-title":"Inform. Comput."},{"key":"37_CR8","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:233\u2013248, 1993.","journal-title":"Disc. Appl. Math."},{"key":"37_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"142","author":"N. Kinnersley","year":"1992","unstructured":"N. Kinnersley. The vertex separation number of a graph equals its path-width. Inform. Process. Lett., 142:345\u2013350, 1992.","journal-title":"Inform. Process. Lett."},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/0012-365X(85)90046-9","volume":"55","author":"L. Kirousis","year":"1985","unstructured":"L. Kirousis and C. Papadimitriou. Interval graphs and searching. Disc. Math., 55:181\u2013184, 1985.","journal-title":"Disc. Math."},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(86)90146-5","volume":"47","author":"L. Kirousis","year":"1986","unstructured":"L. Kirousis and C. Papadimitriou. Searching and pebbling. Theor. Comp. Science, 47:205\u2013218, 1986.","journal-title":"Theor. Comp. Science"},{"issue":"2","key":"37_CR12","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1145\/151261.151263","volume":"40","author":"A. LaPaugh","year":"1993","unstructured":"A. LaPaugh. Recontamination does not help to search a graph. J. Assoc. Comput. Mach., 40(2):243\u2013245, 1993.","journal-title":"J. Assoc. Comput. Mach."},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF00264496","volume":"16","author":"T. Lengauer","year":"1981","unstructured":"T. Lengauer. Black-white pebbles and graph separation. Acta Informat., 16:465\u2013475, 1981.","journal-title":"Acta Informat."},{"key":"37_CR14","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","volume":"23","author":"F. Makedon","year":"1989","unstructured":"F. Makedon and I. Sudborough. On minimizing width in linear layouts. Disc. Appl. Math., 23:243\u2013265, 1989.","journal-title":"Disc. Appl. Math."},{"issue":"1","key":"37_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"N. Megiddo, S. Hakimi, M. Garey, D. Johnson, and C. Papadimitriou. The complexity of searching a graph. J. Assoc. Comput. Mach., 35(1): 18\u201344, 1988.","journal-title":"J. Assoc. Comput. Mach."},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"R. H. Mohring. Graph problems related to gate matrix layout and PLA folding. In E. Mayr, H. Noltmeier, and M. Syslo, editors, Computational Graph Theory, pages 17\u201351. Springer Verlag, 1990.","DOI":"10.1007\/978-3-7091-9076-0_2"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"F. Monien","year":"1988","unstructured":"F. Monien and I. Sudborough. Min cut is NP-complete for edge weighted trees. Theor. Comp. Science, 58:209\u2013229, 1988.","journal-title":"Theor. Comp. Science"},{"key":"37_CR18","first-page":"426","volume-title":"Theory and Applications of Graphs","author":"T. Parsons","year":"1976","unstructured":"T. Parsons. Pursuit-evasion in a graph. In Y. Alavi and D. Lick, editors, Theory and Applications of Graphs, pages 426\u2013441. Springer-Verlag, New York\/Berlin, 1976."},{"key":"37_CR19","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. Seymour. Graph minors. I. Excluding a forest. J. Comb. Theory Series B, 35:39\u201361, 1983.","journal-title":"J. Comb. Theory Series B"},{"key":"37_CR20","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N. Robertson","year":"1985","unstructured":"N. Robertson and P. Seymour. Disjoint paths-A servey. SIAM J. Alg. Disc. Meth., 6:300\u2013305, 1985.","journal-title":"SIAM J. Alg. Disc. Meth."},{"issue":"4","key":"37_CR21","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1145\/4221.4228","volume":"32","author":"M. Yannakakis","year":"1985","unstructured":"M. Yannakakis. A polynomial algorithm for the min-cut linear arrangement of trees. J. Assoc. Comput. Mach., 32(4):950\u2013988, 1985.","journal-title":"J. Assoc. Comput. Mach."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45253-2_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T08:09:43Z","timestamp":1551082183000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45253-2_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540410041","9783540452539"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-45253-2_37","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}