{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:48Z","timestamp":1725664128254},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_240","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:09Z","timestamp":1330261749000},"page":"108-117","source":"Crossref","is-referenced-by-count":11,"title":["Treewidth of circle graphs"],"prefix":"10.1007","author":[{"given":"T.","family":"Kloks","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"12_CR1","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":"12_CR2","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(89)90221-4","volume":"31","author":"H. L. Bodlaender","year":"1989","unstructured":"Bodlaender, H. L., Achromatic number is NP-complete for cographs and interval graphs, Information Processing Letter 31, (1989), pp. 135\u2013138.","journal-title":"Information Processing Letter"},{"key":"12_CR3","volume-title":"Technical report RUU-CS-92-27","author":"H. Bodlaender","year":"1992","unstructured":"Bodlaender, H., A linear time algorithm for finding tree-decompositions of small treewidth, Technical report RUU-CS-92-27, Department of Computer Science, Utrecht University, Utrecht, The Netherlands, (1992)."},{"key":"12_CR4","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."},{"key":"12_CR5","unstructured":"Bodlaender, H. and R. H. M\u00f6hring, The pathwidth and treewidth of cographs, Proceedings 2 nd Scandinavian Workshop on Algorithm Theory, Springer Verlag, Lecture Notes in Computer Science 447, (1990), pp. 301\u2013309."},{"key":"12_CR6","first-page":"569","volume":"300","author":"A. Bouchet","year":"1985","unstructured":"Bouchet, A., A polynomial algorithm for recognizing circle graphs, C. R. Acad. Sci. Paris, S\u00e9r. I Math. 300, (1985), pp. 569\u2013572.","journal-title":"C. R. Acad. Sci. Paris, S\u00e9r. I Math."},{"key":"12_CR7","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF02579301","volume":"7","author":"A. Bouchet","year":"1987","unstructured":"Bouchet, A., Reducing prime graphs and recognizing circle graphs, Combinatorica 7, (1987), pp. 243\u2013254.","journal-title":"Combinatorica"},{"key":"12_CR8","unstructured":"Brandst\u00e4dt, A., Special graph classes \u2014 a survey, Schriftenreihe des Fachbereichs Mathematik, SM-DU-199 (1991), Universit\u00e4t Duisburg Gesamthochschule."},{"key":"12_CR9","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":"12_CR10","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(85)90001-X","volume":"6","author":"M. Farber","year":"1985","unstructured":"Farber, M. and M. Keil, Domination in permutation graphs, J. Algorithms 6, (1985), pp. 309\u2013321.","journal-title":"J. Algorithms"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Gabor, C. P., W. L. Hsu and K. J. Supowit, Recognizing circle graphs in polynomial time, 26th Annual IEEE Symposium on Foundations of Computer Science, (1985).","DOI":"10.1109\/SFCS.1985.47"},{"key":"12_CR12","unstructured":"Gimbel, J., D. Kratsch and L. Stewart, On cocolourings and cochromatic numbers of graphs. To appear in Disc. Appl. Math."},{"key":"12_CR13","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":"12_CR14","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":"12_CR15","doi-asserted-by":"publisher","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":"12_CR16","volume-title":"PhD Thesis","author":"T. Kloks","year":"1993","unstructured":"Kloks, T., Treewidth, PhD Thesis, Utrecht University, The Netherlands, (1993)."},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"Kloks, T. and H. Bodlaender, Approximating treewidth and pathwidth of some classes of perfect graphs, Proceedings Third International Symposium on Algorithms and Computation, ISAAC'92, Springer Verlag, Lecture Notes in Computer Science, 650, (1992), pp. 116\u2013125.","DOI":"10.1007\/3-540-56279-6_64"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Kloks, T., H. Bodlaender, H. M\u00fcller and D. Kratsch, Computing treewidth and minimum fill-in: all you need are the minimal separators. To appear in Proceedings of the First Annual European Symposium on Algorithms, (1993).","DOI":"10.1007\/3-540-57273-2_61"},{"key":"12_CR19","unstructured":"Kloks, T. and D. Kratsch, Treewidth of chordal bipartite graphs, 10th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Lecture Notes in Computer Science 665, (1993), pp. 80\u201389."},{"key":"12_CR20","volume-title":"Computing Science Note, 93\/27","author":"T. Kloks","year":"1993","unstructured":"Kloks, T. and D. Kratsch, Finding all minimal separators of a graph, Computing Science Note, 93\/27, Eindhoven University of Technology, Eindhoven, The Netherlands, (1993)."},{"key":"12_CR21","unstructured":"M\u00fcller, H., Chordal graphs of domino type. Manuscript, (1993)."},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/0012-365X(85)90117-7","volume":"54","author":"W. Naji","year":"1985","unstructured":"Naji, W., Reconnaissance des graphes de cordes, Discrete Mathematics 54, (1985), pp. 329\u2013337.","journal-title":"Discrete Mathematics"},{"key":"12_CR23","unstructured":"Sundaram, R., K. Sher Singh and C. Pandu Rangan, Treewidth of circular arc graphs. To appear in SIAM J. Disc. Math."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1109\/TCAD.1987.1270250","volume":"6","author":"K. J. Supowit","year":"1987","unstructured":"Supowit, K. J., Finding a maximum planar subset of a set of nets in a channel, IEEE Trans. Computer Aided Design 6, (1987), pp. 93\u201394.","journal-title":"IEEE Trans. Computer Aided Design"},{"key":"12_CR25","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0020-0190(85)90093-6","volume":"21","author":"K. J. Supowit","year":"1985","unstructured":"Supowit, K. J., Decomposing a set of points into chains, with applications to permutation and circle graphs, Information Processing Letters 21, (1985), pp. 249\u2013252.","journal-title":"Information Processing Letters"},{"key":"12_CR26","first-page":"633","volume":"20","author":"K. Wagner","year":"1984","unstructured":"Wagner, K., Monotonic coverings of finite sets, Journal of Information Processing and Cybernetics, EIK, 20, (1984), pp. 633\u2013639.","journal-title":"Journal of Information Processing and Cybernetics, EIK"},{"key":"12_CR27","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 and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_240.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:07Z","timestamp":1605647587000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_240","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}