{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:13:39Z","timestamp":1725484419806},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438663"},{"type":"electronic","value":"9783540454717"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45471-3_40","type":"book-chapter","created":{"date-parts":[[2007,5,21]],"date-time":"2007-05-21T13:18:22Z","timestamp":1179753502000},"page":"388-397","source":"Crossref","is-referenced-by-count":1,"title":["Computing the Treewidth and the Minimum Fill-in with the Modular Decomposition"],"prefix":"10.1007","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Udi","family":"Rotics","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,21]]},"reference":[{"key":"40_CR1","doi-asserted-by":"publisher","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-A survey. BIT, 25:2\u201323, 1985.","journal-title":"BIT"},{"key":"40_CR2","doi-asserted-by":"publisher","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:277\u2013284, 1987.","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(98)00115-2","volume":"89","author":"L. Babel","year":"1998","unstructured":"L. Babel. Triangulating graphs with few P 4\u2019s. Disc. Appl. Math., 89:45\u201357, 1998.","journal-title":"Disc. Appl. Math."},{"issue":"4","key":"40_CR4","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1137\/S089548019223992X","volume":"8","author":"H. L. Bodlaender","year":"1995","unstructured":"H. L. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidth of permutation graphs. SIAM J. Disc. Math., 8(4):606\u2013616, 1995.","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR5","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. M\u00f6hring. The pathwidth and treewidth of cographs. SIAM J. Disc. Math., 6:181\u2013188, 1993.","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR6","volume-title":"Technical Report CS-UU-2001-22, Institute of Information and Computing Sciences","author":"H. L. Bodlaender","year":"2001","unstructured":"H. L. Bodlaender and U. Rotics. Computing the treewidth and the minimum fill-in with the modular decomposition. Technical Report CS-UU-2001-22, Institute of Information and Computing Sciences, Utrecht University, Utrecht, the Netherlands, 2001. ftp:\/\/ftp.cs.uu.nl\/pub\/RUU\/CS\/techreps\/CS-2001\/2001-22.pdf ."},{"key":"40_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/3-540-46541-3_42","volume-title":"Proceedings STACS\u201900","author":"V. Bouchitt\u00e9","year":"2000","unstructured":"V. Bouchitt\u00e9 and I. Todinca. Listing all potential maximal cliques of a graph. In H. Reidel and S. Tison, editors, Proceedings STACS\u201900, pages 503\u2013515. Springer Verlag, Lecture Notes in Computer Science, vol. 1770, 2000."},{"key":"40_CR8","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1137\/S0097539799359683","volume":"31","author":"V. Bouchitt\u00e9","year":"2001","unstructured":"V. Bouchitt\u00e9 and I. Todinca. Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput., 31:212\u2013232, 2001.","journal-title":"SIAM J. Comput."},{"key":"40_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BFb0024492","volume-title":"Proceedings 23nd International Workshop on Graph-Theoretic Concepts in Computer Science WG\u201997","author":"H. Broersma","year":"1997","unstructured":"H. Broersma, E. Dahlhaus, and T. Kloks. Algorithms for the treewidth and minimum fill-in of HHD-free graphs. In Proceedings 23nd International Workshop on Graph-Theoretic Concepts in Computer Science WG\u201997, pages 109\u2013117. Springer Verlag, Lecture Notes in Computer Science, vol. 1335, 1997."},{"key":"40_CR10","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/S0166-218X(99)00146-8","volume":"99","author":"H. Broersma","year":"2000","unstructured":"H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimum fill in and treewidth for distance hereditary graphs. Disc. Appl. Math., 99:367\u2013400, 2000.","journal-title":"Disc. Appl. Math."},{"issue":"2","key":"40_CR11","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1287\/moor.8.2.170","volume":"8","author":"B. H","year":"1983","unstructured":"H. Buer and R. H. M\u00f6hring. A fast algorithm for the decomposition of graphs and posets. Mathematics of Operations Research, 8(2):170\u2013184, 1983.","journal-title":"Mathematics of Operations Research"},{"key":"40_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/BFb0017474","volume-title":"Trees in algebra and programming, CAAP\u201994","author":"A. Cournier","year":"1994","unstructured":"A. Cournier and M. Habib. A new linear algorithm for modular decomposition. In T. Sophie, editor, Trees in algebra and programming, CAAP\u201994, pages 68\u201384. Springer Verlag, Lecture Notes in Computer Science, vol. 787, 1994."},{"key":"40_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/10692760_28","volume-title":"Proceedings 24nd International Workshop on Graph-Theoretic Concepts in Computer Science WG\u201998","author":"E. Dahlhaus","year":"1998","unstructured":"E. Dahlhaus. Minimum fill-in and treewidth for graphs modularly decomposable into chordal graphs. In Proceedings 24nd International Workshop on Graph-Theoretic Concepts in Computer Science WG\u201998, pages 351\u2013358. Springer Verlag, Lecture Notes in Computer Science, vol. 1517, 1998."},{"key":"40_CR14","unstructured":"E. Dahlhaus, J. Gustedt, and R. M. McConnell. Efficient and practical modular decomposition. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 26\u201335, 1997."},{"key":"40_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/3-540-44634-6_9","volume-title":"Proceedings WADS 2001","author":"W. Espelage","year":"2001","unstructured":"W. Espelage, F. Gurski, and E. Wanke. Deciding clique-width for graphs of bounded treewidth. In Proceedings WADS 2001, pages 87\u201398. Springer Verlag, Lecture Notes in Computer Science, vol. 2125, 2001."},{"key":"40_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1142\/S0129054196000099","volume":"7","author":"T. Kloks","year":"1996","unstructured":"T. Kloks. Treewidth of circle graphs. Int. J. Found. Computer Science, 7:111\u2013120, 1996.","journal-title":"Int. J. Found. Computer Science"},{"issue":"3","key":"40_CR17","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S009753979427087X","volume":"27","author":"T. Kloks","year":"1998","unstructured":"T. Kloks and D. Kratsch. Listing all minimal separators of a graph. SIAM J. Comput., 27(3):605\u2013613, 1998.","journal-title":"SIAM J. Comput."},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0012-365X(98)00319-7","volume":"201","author":"R. M. McConnell","year":"1999","unstructured":"R. M. McConnell and J. Spinrad. Modular decomposition and transitive orientation. Disc. Math., 201:189\u2013241, 1999.","journal-title":"Disc. Math."},{"key":"40_CR19","doi-asserted-by":"crossref","unstructured":"R. H. M\u00f6hring. Graph problems related to gate matrix layout and PLA folding. In E. Mayr, H. Noltemeier, and M. SysFlo, editors, Computational Graph Theory, Comuting Suppl. 7, pages 17\u201351. Springer Verlag, 1990.","DOI":"10.1007\/978-3-7091-9076-0_2"},{"key":"40_CR20","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":"40_CR21","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1137\/S0895480191193789","volume":"7","author":"R. Sundaram","year":"1994","unstructured":"R. Sundaram, K. Sher Singh, and C. Pandu Rangan. Treewidth of circular-arc graphs. SIAM J. Disc. Math., 7:647\u2013655, 1994.","journal-title":"SIAM J. Disc. Math."},{"key":"40_CR22","doi-asserted-by":"publisher","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 J. Alg. Disc. Meth., 2:77\u201379, 1981.","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45471-3_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T02:42:18Z","timestamp":1556419338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45471-3_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438663","9783540454717"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-45471-3_40","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}