{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:26:31Z","timestamp":1759638391603},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540412557"},{"type":"electronic","value":"9783540409960"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-40996-3_17","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:17:32Z","timestamp":1188335852000},"page":"192-203","source":"Crossref","is-referenced-by-count":23,"title":["Constructive Linear Time Algorithms for Small Cutwidth and Carving-Width"],"prefix":"10.1007","author":[{"given":"Dimitrios M.","family":"Thilikos","sequence":"first","affiliation":[]},{"given":"Maria J.","family":"Serna","sequence":"additional","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,1,29]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"K. R. Abrahamson and M. R. Fellows. Finite automata, bounded treewidth and well-quasiordering. In N. Robertson and P. Seymour, editors, Proceedings of the AMS Summer Workshop on Graph Minors, Graph Structure Theory, Contemporary Mathematics vol. 147, pages 539\u2013564. American Mathematical Society, 1993.","DOI":"10.1090\/conm\/147\/01199"},{"key":"17_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 path-width and treewidth of graphs. J. Algorithms, 21:358\u2013402, 1996.","journal-title":"J. Algorithms"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0166-218X(94)90018-3","volume":"54","author":"H. L. Bodlaender","year":"1994","unstructured":"H. L. Bodlaender. Improved self-reduction algorithms for graphs with bounded treewidth. Disc. Appl. Math., 54:101\u2013115, 1994.","journal-title":"Disc. Appl. Math."},{"key":"17_CR4","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender. A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25:1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"17_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1007\/3-540-63165-8_217","volume-title":"Constructive linear time algorithms for branchwidth","author":"H. L. Bodlaender","year":"1997","unstructured":"H. L. Bodlaender and D. M. Thilikos. Constructive linear time algorithms for branchwidth. In P. Degano, R. Gorrieri, and A. Marchetti-Spaccamela, editors, Proceedings 24th International Colloquium on Automata, Languages, and Programming, ICALP\u201997, pages 627\u2013637. Springer-Verlag, Lecture Notes in Computer Science, Vol. 1256, 1997."},{"key":"17_CR6","unstructured":"H. L. Bodlaender and D. M. Thilikos. Computing small search numbers in linear time. Technical Report Technical Report No. UU-CS-1998-05, Dept. of Computer Science, Utrecht University, 1998."},{"key":"17_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1137\/0606026","volume":"6","author":"F. R. K. Chung","year":"1985","unstructured":"F. R. K. Chung. On the cutwidth and topological bandwidth of a tree. SIAM J. Alg. Disc. Meth., 6:268\u2013277, 1985.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0012-365X(89)90083-6","volume":"75","author":"F. R. K. Chung","year":"1989","unstructured":"F. R. K. Chung and P. D. Seymour. Graphs with small bandwidth and cutwidth. Disc. Math., 75:113\u2013119, 1989.","journal-title":"Disc. Math."},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"G. Even, J. Naor, S. Rao, and B. Schieber. Divide-and-conquer approximation algorithms via spreading metrics. In Proc. 36th Symp. on Foundations of Computer Science (FOCS), pages 62\u201371, 1995.","DOI":"10.1109\/SFCS.1995.492463"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1137\/0405010","volume":"5","author":"M. R. Fellows","year":"1992","unstructured":"M. R. Fellows and M. A. Langston. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. Disc. Meth., 5:117\u2013126, 1992.","journal-title":"SIAM J. Disc. Meth."},{"key":"17_CR11","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1016\/S0022-0000(05)80079-0","volume":"49","author":"M. R. Fellows","year":"1994","unstructured":"M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. J. Comp. Syst. Sc., 49:769\u2013779, 1994.","journal-title":"J. Comp. Syst. Sc."},{"key":"17_CR12","volume-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York, 1979."},{"key":"17_CR13","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0020-0190(94)90044-2","volume":"50","author":"S. Khuller","year":"1994","unstructured":"S. Khuller, B. Raghavachari, and N. Young. Designing multi-commodity flow trees. Inform. Proc. Letters, 50:49\u201355, 1994.","journal-title":"Inform. Proc. Letters"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0166-218X(93)90171-J","volume":"43","author":"E. Korach","year":"1993","unstructured":"E. Korach and N. Solel. Tree-width, path-width and cutwidth. Disc. Appl. Math., 43:97\u2013101, 1993.","journal-title":"Disc. Appl. Math."},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1137\/0606044","volume":"6","author":"F. S. Makedon","year":"1985","unstructured":"F. S. Makedon, C. H. Papadimitriou, and I. H. Sudborough. Topological bandwidth. SIAM J. Alg. Disc. Meth., 6:418\u2013444, 1985.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"17_CR16","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0166-218X(89)90016-4","volume":"23","author":"F. S. Makedon","year":"1989","unstructured":"F. S. Makedon and I. H. Sudborough. On minimizing width in linear layouts. Disc. Appl. Math., 23:243\u2013265, 1989.","journal-title":"Disc. Appl. Math."},{"key":"17_CR17","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. Theor. Comp. Sc., 58:209\u2013229, 1988.","journal-title":"Theor. Comp. Sc."},{"key":"17_CR18","unstructured":"N. Robertson and P. D. Seymour. Graph minors. XXIII. the Nash-Williams immersion conjecture. To appear."},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N. Robertson","year":"1995","unstructured":"N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Comb. Theory Series B, 63:65\u2013110, 1995.","journal-title":"J. Comb. Theory Series B"},{"issue":"2","key":"17_CR20","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/BF01215352","volume":"14","author":"P. D. Seymour","year":"1994","unstructured":"P. D. Seymour and R. Thomas. Call routing and the ratcatcher. Combinatorica, 14(2):217\u2013241, 1994.","journal-title":"Combinatorica"},{"key":"17_CR21","doi-asserted-by":"publisher","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. ACM, 32:950\u2013988, 1985.","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-40996-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T00:40:26Z","timestamp":1550882426000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-40996-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540412557","9783540409960"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-40996-3_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}