{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:00:40Z","timestamp":1725663640395},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540572732"},{"type":"electronic","value":"9783540480327"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57273-2_61","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T07:37:05Z","timestamp":1330241825000},"page":"260-271","source":"Crossref","is-referenced-by-count":25,"title":["Computing treewidth and minimum fill-in: All you need are the minimal separators"],"prefix":"10.1007","author":[{"given":"T.","family":"Kloks","sequence":"first","affiliation":[]},{"given":"H.","family":"Bodlaender","sequence":"additional","affiliation":[]},{"given":"H.","family":"M\u00fcller","sequence":"additional","affiliation":[]},{"given":"D.","family":"Kratsch","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"23_CR1","unstructured":"Anand, R., H. Balakrishnan and C. Pandu Rangan, Treewidth of distance hereditary graphs, To appear."},{"key":"23_CR2","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/BF01934985","volume":"25","author":"S. Arnborg","year":"1985","unstructured":"Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability \u2014 A survey. BIT 25, (1985), pp. 2\u201323.","journal-title":"BIT"},{"key":"23_CR3","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"Arnborg, S., 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":"23_CR4","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"Arnborg, S. and A. Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math. 23, (1989), pp. 11\u201324.","journal-title":"Disc. Appl. Math."},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"B 41","author":"H. J. Bandelt","year":"1986","unstructured":"Bandelt, H. J. and H. M. Mulder, Distance-Hereditary Graphs, Journal of Combinatorial Theory, Series B 41, (1986), pp. 182\u2013208.","journal-title":"Journal of Combinatorial Theory, Series"},{"key":"23_CR6","unstructured":"Bodlaender, H., Classes of graphs with bounded treewidth, Technical Report RUU-CS-86-22, Department of Computer Science, Utrecht University, 1986."},{"key":"23_CR7","volume-title":"Technical report RUU-CS-92-12","author":"H. Bodlaender","year":"1992","unstructured":"Bodlaender, H., A tourist guide through treewidth, Technical report RUU-CS-92-12, Department of Computer Science, Utrecht University, Utrecht, The Netherlands, 1992. To appear in: Acta Cybernetica."},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Bodlaender, H., A linear time algorithm for finding tree-decompositions of small treewidth, In Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 226\u2013234.","DOI":"10.1145\/167088.167161"},{"key":"23_CR9","volume-title":"Technical report RUU-CS-92-30","author":"H. Bodlaender","year":"1992","unstructured":"Bodlaender, H., T. Kloks and D. Kratsch, Treewidth and pathwidth of permutation graphs, Technical report RUU-CS-92-30, Department of Computer Science, Utrecht University, Utrecht, The Netherlands, (1992). To appear in: Proceedings of the 20 th International Colloquium on Automata, Languages and Programming (1993)."},{"key":"23_CR10","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-52846-6_99","volume":"447","author":"H. Bodlaender","year":"1990","unstructured":"Bodlaender, H. and R. H. M\u00f6hring, The pathwidth and treewidth of cographs, In Proceedings 2nd Scandinavian Workshop on Algorithm Theory, Springer Verlag, Lecture Notes in Computer Science 447, (1990), pp. 301\u2013309.","journal-title":"Springer Verlag, Lecture Notes in Computer Science"},{"key":"23_CR11","unstructured":"Brandst\u00e4dt, A., Special graph classes \u2014 a survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199 (1991), Universit\u00e4t-Gesamthochschule Duisburg."},{"key":"23_CR12","first-page":"249","volume":"43","author":"D. G. Corneil","year":"1984","unstructured":"Corneil, D. G., Y. Perl, L. K. Stewart, Cographs: recognition, applications and algorithms, Congressus Numerantium, 43 (1984), pp. 249\u2013258.","journal-title":"Congressus Numerantium"},{"key":"23_CR13","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G. A. Dirac","year":"1961","unstructured":"Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25, (1961), pp. 71\u201376.","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"23_CR14","unstructured":"Garey, M. R. and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, San Francisco, 1979."},{"key":"23_CR15","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"Golumbic, M. C., Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"23_CR16","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0012-365X(83)90019-5","volume":"43","author":"M. C. Golumbic","year":"1983","unstructured":"Golumbic, M. C., D. Rotem, J. Urrutia, Comparability graphs and intersection graphs, Discrete Mathematics 43, (1983), pp. 37\u201346.","journal-title":"Discrete Mathematics"},{"key":"23_CR17","unstructured":"Gustedt, J., On the pathwidth of chordal graphs, To appear in Discrete Applied Mathematics."},{"key":"23_CR18","unstructured":"Habib, M. and R. H. M\u00f6hring, Treewidth of cocomparability graphs and a new order-theoretic parameter, Technical Report 336\/1992, Technische Universit\u00e4t Berlin, 1992."},{"key":"23_CR19","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1016\/0196-6774(85)90012-4","volume":"6","author":"D. S. Johnson","year":"1985","unstructured":"Johnson, D. S., The NP-completeness column: An ongoing guide, J. Algorithms 6, (1985), pp. 434\u2013451.","journal-title":"J. Algorithms"},{"key":"23_CR20","volume-title":"Ph.D. Thesis","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., Treewidth, Ph.D. Thesis, Utrecht University, The Netherlands, 1993."},{"key":"23_CR21","doi-asserted-by":"crossref","unstructured":"Kloks, T., Minimum fill-in for chordal bipartite graphs, Technical Report RUU-CS-93-11, Department of Computer Science, Utrecht University, 1993.","DOI":"10.1007\/3-540-56503-5_11"},{"key":"23_CR22","doi-asserted-by":"crossref","unstructured":"Kloks, T., Treewidth of circle graphs, Technical Report RUU-CS-93-12, Department of Computer Science, Utrecht University, 1993.","DOI":"10.1007\/3-540-57568-5_240"},{"key":"23_CR23","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/3-540-56503-5_11","volume":"665","author":"T. Kloks","year":"1993","unstructured":"Kloks, T. and D. Kratsch, Treewidth of chordal bipartite graphs, 10 th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Lecture Notes in Computer Science 665, (1993), pp. 80\u201389.","journal-title":"Springer-Verlag, Lecture Notes in Computer Science"},{"key":"23_CR24","unstructured":"M\u00f6hring, R. H., private communication."},{"key":"23_CR25","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0304-3975(88)90028-X","volume":"58","author":"B. Monien","year":"1988","unstructured":"Monien, B. and I. H. Sudborough, Min Cut is NP-complete for Edge Weighted Trees, Theoretical Computer Science 58 (1988), pp. 209\u2013229.","journal-title":"Theoretical Computer Science"},{"key":"23_CR26","doi-asserted-by":"crossref","first-page":"597","DOI":"10.1016\/0022-247X(70)90282-9","volume":"32","author":"D. J. Rose","year":"1970","unstructured":"Rose, D. J., Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32 (1970), pp. 597\u2013609.","journal-title":"J. Math. Anal. Appl."},{"key":"23_CR27","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/S0166-218X(87)80003-3","volume":"18","author":"J. Spinrad","year":"1987","unstructured":"Spinrad, J., A. Brandst\u00e4dt, L. Stewart, Bipartite permutation graphs, Discrete Applied Mathematics, 18 (1987), pp. 279\u2013292.","journal-title":"Discrete Applied Mathematics"},{"key":"23_CR28","unstructured":"Sundaram, R., K. Sher Singh and C. Pandu Rangan, Treewidth of circular arc graphs, To appear in SIAM Journal on Discrete Mathematics."},{"key":"23_CR29","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R. E. Tarjan","year":"1985","unstructured":"Tarjan, R. E., Decomposition by clique separators, Discrete Mathematics 55 (1985), pp. 221\u2013232.","journal-title":"Discrete Mathematics"},{"key":"23_CR30","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1137\/0602010","volume":"2","author":"M. Yannakakis","year":"1981","unstructured":"Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. Alg. Disc. Meth. 2, (1981), pp. 77\u201379.","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Algorithms\u2014ESA '93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57273-2_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:10:42Z","timestamp":1605629442000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57273-2_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540572732","9783540480327"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-57273-2_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}