{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T20:35:18Z","timestamp":1762806918073},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667315"},{"type":"electronic","value":"9783540467847"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46784-x_16","type":"book-chapter","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T12:02:55Z","timestamp":1175774575000},"page":"155-166","source":"Crossref","is-referenced-by-count":4,"title":["Efficient Analy sis of Graphs with Small Minimal Separators"],"prefix":"10.1007","author":[{"given":"K.","family":"Skodinis","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S. Arnborg","year":"1987","unstructured":"S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM J. Alg. Disc. Meth., 8:277\u2013284, 1987. 155, 156, 158","journal-title":"SIAM J. Alg. Disc. Meth."},{"key":"16_CR2","doi-asserted-by":"publisher","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. Algorithms, 12:308\u2013340, 1991. 155","journal-title":"J. Algorithms"},{"key":"16_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/0166-218X(89)90031-0","volume":"23","author":"S. Arnborg","year":"1989","unstructured":"S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees. Disc. Appl. Math., 23:11\u201324, 1989. 155","journal-title":"Disc. Appl. Math."},{"key":"16_CR4","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1007\/3-540-19488-6_110","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming","author":"H. Bodlaender","year":"1988","unstructured":"H. Bodlaender. Dynamic programming algorithms on graphs with bounded treewidth. In Proceedings of the International Colloquium on Automata, Languages and Programming, volume 317 of Lect. Notes in Comput. Sci., pages 105\u2013119. Springer-Verlag, New York\/Berlin, 1988. 159"},{"issue":"6","key":"16_CR5","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. 155, 158, 162, 163","journal-title":"SIAM J. Comput."},{"key":"16_CR6","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. 155, 159","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR7","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1137\/0406014","volume":"6","author":"H. Bodlaender","year":"1993","unstructured":"H. Bodlaender and R. M\u00f6hring. The pathwidth and treewidth of cographs. SIAM J. Disc. Math., 6:181\u2013188, 1993. 155, 159","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/BF01758777","volume":"7","author":"R. Borie","year":"1992","unstructured":"R. Borie, R. Parker, and C. Tovey. Automatic generation of liner-time algorithms from predicate calculus describtions of problems on recursively constructed graph families. Algorithmica, 7:555\u2013581, 1992. 155","journal-title":"Algorithmica"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"A. Brandst\u00e4dt. Graphen und Algorithmen. B. G. Teubner, Stuttgard, 1994. 158","DOI":"10.1007\/978-3-322-94689-8"},{"key":"16_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0012-365X(77)90030-9","volume":"19","author":"F. Gavril","year":"1977","unstructured":"F. Gavril. Algorithms on clique separable graphs. Disc. Math., 19:159\u2013165, 1977. 159","journal-title":"Disc. Math."},{"key":"16_CR11","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"M. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980. 156, 158"},{"issue":"4","key":"16_CR12","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A. Itai","year":"1982","unstructured":"A. Itai, C. Papadimitriou, and J. Szwarcfiter. Hamilton paths in grid graphs. SIAM J. Comput., 11(4):676\u2013686, 1982. 164","journal-title":"SIAM J. Comput."},{"key":"16_CR13","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0045375","volume-title":"Treewidth. Computations and Approximations","author":"T. Kloks","year":"1994","unstructured":"T. Kloks. Treewidth. Computations and Approximations, volume 842 of Lect. Notes in Comput. Sci. Springer-Verlag, New York\/Berlin, 1994. 155, 158"},{"key":"16_CR14","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/3-540-57273-2_61","volume-title":"Proceedings of the European Symposium on Algorithms","author":"T. Kloks","year":"1993","unstructured":"T. Kloks, H. Bodlaender, H. M\u00fcller, and D. Kratsch. Computing treewidth and minimum fill-in: All you need are the minimal separators. In Proceedings of the European Symposium on Algorithms, volume 726 of Lect. Notes in Comput. Sci., pages 260\u2013271. Springer-Verlag, New York\/Berlin, 1993. 156"},{"key":"16_CR15","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1007\/BFb0049435","volume-title":"Proceedings of the European Symposium on Algorithms","author":"T. Kloks","year":"1994","unstructured":"T. Kloks, H. Bodlaender, H. M\u00fcller, and D. Kratsch. Erratum to the ESA\u201993 proceedings. In Proceedings of the European Symposium on Algorithms, volume 855 of Lect. Notes in Comput. Sci., page 508. Springer-Verlag, New York\/Berlin, 1994. 156"},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1006\/jagm.1995.1037","volume":"19","author":"T. Kloks","year":"1995","unstructured":"T. Kloks and D. Kratsch. Treewidth of chordal bipartite graphs. J. Algorithms, 19:266\u2013281, 1995. 155, 159","journal-title":"J. Algorithms"},{"issue":"3","key":"16_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. 156","journal-title":"SIAM J. Comput."},{"key":"16_CR18","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994. 164"},{"key":"16_CR19","series-title":"Lect. Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/3-540-60084-1_68","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming","author":"A. Parra","year":"1995","unstructured":"A. Parra and P. Scheffler. How to use the minimal separators of a graph for its chordal triangulation. In Proceedings of the International Colloquium on Automata, Languages and Programming, volume 944 of Lect. Notes in Comput. Sci., pages 123\u2013134. Springer-Verlag, New York\/Berlin, 1995. 156"},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0095-8956(91)90061-N","volume":"52","author":"N. Robertson","year":"1991","unstructured":"N. Robertson and P. Seymour. Graph minors X. Obstructions to treedecompositions. J. Comb. Theory Series B, 52:153\u2013190, 1991. 155, 159","journal-title":"J. Comb. Theory Series B"},{"key":"16_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. 155, 159","journal-title":"SIAM J. Disc. Math."},{"key":"16_CR22","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0012-365X(85)90051-2","volume":"55","author":"R. Tarjan","year":"1985","unstructured":"R. Tarjan. Decomposition by clique separators. Disc. Math., 55:221\u2013232, 1985. 157, 159, 163","journal-title":"Disc. Math."}],"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-46784-X_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T07:16:16Z","timestamp":1550301376000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46784-X_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667315","9783540467847"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-46784-x_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}