{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:17Z","timestamp":1759638017571},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540551218"},{"type":"electronic","value":"9783540467359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-55121-2_1","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T04:47:24Z","timestamp":1330231644000},"page":"1-12","source":"Crossref","is-referenced-by-count":16,"title":["Approximating treewidth, pathwidth, and minimum elimination tree height"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[]},{"given":"John R.","family":"Gilbert","sequence":"additional","affiliation":[]},{"given":"Hj\u00e1lmt\u00fdr","family":"Hafsteinsson","sequence":"additional","affiliation":[]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,5]]},"reference":[{"key":"1_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, A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277\u2013284, 1987.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"},{"key":"1_CR2","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/0196-6774(91)90006-K","volume":"12","author":"S. Arnborg","year":"1991","unstructured":"S. Arnborg, J. Lagergren, and D. Seese. Easy problems for tree-decomposable graphs, J. of Algorithms, 12:308\u2013340, 1991.","journal-title":"J. of Algorithms"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"S. Arnborg. Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"1_CR4","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1016\/0196-6774(90)90013-5","volume":"11","author":"H. L. Bodlaender","year":"1990","unstructured":"H. L. Bodlaender. Polynomial algorithms for Graph Isomorphism and Chromatic Index on partial k-trees. J. Algorithms, 11:631\u2013644, 1990.","journal-title":"J. Algorithms"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender and T. Kloks. Better algorithms for the pathwidth and treewidth of graphs. Proc. 18th ICALP, pages 544\u2013555. Springer Verlag, Lect. Notes in Comp. Sc. 510, 1991.","DOI":"10.1007\/3-540-54233-7_162"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"H. L. Bodlaender and R. H. M\u00f6hring. The pathwidth and treewidth of cographs. In Proc. 2nd Scandinavian Workshop on Algorithm Theory, pages 301\u2013309. Springer Verlag Lect. Notes in Computer Science vol. 447, 1990.","DOI":"10.1007\/3-540-52846-6_99"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1109\/TCAD.1987.1270248","volume":"6","author":"N. Deo","year":"1987","unstructured":"N. Deo, M. S. Krishnamoorty and M. A. Langston. Exact and approximate solutions for the gate matrix layout problem. IEEE Transactions on Computer-Aided Design, 6:79\u201384, 1987.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"key":"1_CR8","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1109\/TCAD.1984.1270075","volume":"3","author":"J.R. Egan","year":"1984","unstructured":"J.R. Egan and C.L. Liu. Bipartite folding and partitioning of a PLA, IEEE Trans. CAD, 3:191\u2013199, 1984.","journal-title":"IEEE Trans. CAD"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1145\/356044.356047","volume":"9","author":"I. S. Duff","year":"1983","unstructured":"I. S. Duff and J. K. Reid. The multifrontal solution of indefinite sparse symmetric linear equations. ACM Transactions on Mathematical Software, 9:302\u2013325, 1983.","journal-title":"ACM Transactions on Mathematical Software"},{"key":"1_CR10","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979."},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"J. A. George","year":"1973","unstructured":"J. A. George. Nested dissection of a regular finite element mesh. SIAM Journal of Numerical Analysis, 10:345\u2013363, 1973.","journal-title":"SIAM Journal of Numerical Analysis"},{"key":"1_CR12","first-page":"325","volume":"6","author":"J. R. Gilbert","year":"1987\/88","unstructured":"J. R. Gilbert. Some nested dissection order is nearly optimal. Information Processing Letters, 6:325\u2013328, 1987\/88.","journal-title":"Information Processing Letters"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"F. Harary. Graph Theory, Addison-Wesley, 1969.","DOI":"10.21236\/AD0705364"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"P. Klein, A. Agrawal, R. Ravi, and S. Rao. Approximation through multicommodity flow. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science, IEEE, pages 726\u2013737, 1990.","DOI":"10.1109\/FSCS.1990.89595"},{"key":"1_CR15","volume-title":"Theorie der Graphen","author":"D. K\u00f6nig","year":"1950","unstructured":"D. K\u00f6nig. Theorie der Graphen, Reprinted by Chelsea Publishing Company, New York, 1950."},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"J. Lagergren. Efficient parallel algorithms for tree-decomposition and related problems. In Proceedings of the 31th Annual Symposium on Foundations of Computer Science, IEEE, pages 173\u2013182, 1990.","DOI":"10.1109\/FSCS.1990.89536"},{"key":"1_CR17","volume-title":"Handbook of Theoretical Computer Science. A: Algorithms and Complexity Theory","author":"J. Leeuwen van","year":"1990","unstructured":"J. van Leeuwen. Graph Algorithms. In Handbook of Theoretical Computer Science. A: Algorithms and Complexity Theory, North Holland, Amsterdam, 1990."},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"F. T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximate algorithms. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, IEEE pages 422\u2013431, 1988.","DOI":"10.1109\/SFCS.1988.21958"},{"key":"1_CR19","unstructured":"F. T. Leighton. Personal communication, 1990."},{"key":"1_CR20","unstructured":"C. E. Leiserson and J. G. Lewis. Orderings for parallel sparse symmetric factorization. An unpublished manuscript, 1988."},{"key":"1_CR21","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R. J. Lipton","year":"1979","unstructured":"R. J. Lipton, D. J. Rose and R. E. Tarjan. Generalized nested dissection. SIAM Journal of Numerical Analysis 16:346\u2013358, 1979.","journal-title":"SIAM Journal of Numerical Analysis"},{"key":"1_CR22","unstructured":"J. W. H. Liu. The multifrontal method for sparse matrix solution: theory and practice. Tech. Report CS-90-04, York University, North York, Ontario, Canada. To appear."},{"key":"1_CR23","first-page":"17","volume-title":"Computing Supplementum 7","author":"R. H. M\u00f6hring","year":"1990","unstructured":"R. H. M\u00f6hring. Graph problems related to gate matrix layout and PLA folding. In Computing Supplementum 7 (G. Tinhofer et al, eds), page 17\u201351. Springer-Verlag, Vienna, 1990."},{"key":"1_CR24","unstructured":"A. Pothen. The complexity of optimal elimination trees. Tech. Report CS-88-16, Pennsylvania State University, 1988."},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms, 7:309\u2013322, 1986.","journal-title":"J. Algorithms"},{"key":"1_CR26","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. Manuscript, 1986.","DOI":"10.1016\/0095-8956(86)90031-6"},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"N. Robertson and P. D. Seymour. Graph minors. X. Obstructions to tree-decompositions. To appear in J. Combinatorial Theory, Ser. B., 1991.","DOI":"10.1016\/0095-8956(91)90061-N"},{"issue":"No.2","key":"1_CR28","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan and G.S. Lueker. Algorithmic aspects of vertex elimination on graphs. SIAM J. Comput. Vol. 5, No. 2, 266\u2013283, 1976.","journal-title":"SIAM J. Comput."},{"key":"1_CR29","unstructured":"P.D. Seymour and R. Thomas. Call Routing and the Ratcatcher. Manuscript, 1991."},{"key":"1_CR30","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal of Algebraic and Discrete Methods, 2:77\u201379, 1981.","journal-title":"SIAM Journal of Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-55121-2_1.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:57:34Z","timestamp":1605628654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-55121-2_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540551218","9783540467359"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-55121-2_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}