{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:09:21Z","timestamp":1760202561088},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540427070"},{"type":"electronic","value":"9783540454779"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45477-2_9","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T07:09:01Z","timestamp":1187248141000},"page":"78-90","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["On the Relationship between Clique-Width and Treewidth"],"prefix":"10.1007","author":[{"given":"Derek G.","family":"Corneil","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":[[2001,10,2]]},"reference":[{"key":"9_CR1","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, \u201cComplexity of finding embeddings in a k-tree\u201d SIAM J. Alg. Discrete Methods 8 (1987) 277\u2013284.","journal-title":"SIAM J. Alg. Discrete Methods"},{"key":"9_CR2","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender, \u201cA linear time algorithm for finding tree-decompositions of small treewidth\u201d SIAM J. Comput. 25 (1996) 1305\u20131317.","journal-title":"SIAM J. Comput."},{"key":"9_CR3","unstructured":"A. Brandst\u00e4dt and V.V. Lozin, \u201cOn the linear structure and clique-width of bipartite permutation graphs\u201d Rutcor Research Report 29-2001 (2001)."},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"D. G. Corneil, M. Habib, J. M. Lanlignel, B. Reed and U. Rotics, \u201cPolynomial time recognition of clique-width \u2264 3 graphs (Extended Abstract)\u201d accepted to Latin American Theoretical INformatic, LATIN\u20192000.","DOI":"10.1007\/10719839_14"},{"key":"9_CR5","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"D. G. Corneil","year":"1985","unstructured":"D. G. Corneil, Y. Perl and L. Stewart, \u201cA linear recognition algorithm for cographs\u201d SIAM J. Comput. 14 (1985) 926\u2013934.","journal-title":"SIAM J. Comput."},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, J. Engelfriet and G. Rozenberg, \u201cHandle-rewriting hypergraphs grammars\u201d J. Comput. System Sci. 46 (1993) 218\u2013270.","journal-title":"J. Comput. System Sci."},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle, J.A. Makowsky and U. Rotics, \u201cLinear time solvable optimization problems on graphs of bounded clique-width\u201d Theory of Computing Systems 33 (2000) 125\u2013150.","journal-title":"Theory of Computing Systems"},{"key":"9_CR8","unstructured":"B. Courcelle, J.A. Makowsky, and U. Rotics, \u201cOn the fixed parameter complexity of graph enumeration problems definable in monadic second order logic\u201d to appear in Disc. Appl. Math."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle and S. Olariu, \u201cUpper bounds to the clique-width of graphs\u201d Disc. Appl. Math. 101 (2000) 77\u2013114.","journal-title":"Disc. Appl. Math."},{"key":"9_CR10","unstructured":"M.U. Gerber and D. Kobler, \u201cAlgorithms for vertex partitioning problems on graphs with fixed clique-width\u201d submitted (2000)."},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1142\/S0129054100000260","volume":"11","author":"M.C. Golumbic","year":"2000","unstructured":"M.C. Golumbic and U. Rotics, \u201cOn the clique-width of some perfect graph classes\u201d Internat. J. Found. Comput. Sci 11 (2000) 423\u2013443.","journal-title":"Internat. J. Found. Comput. Sci"},{"key":"9_CR12","first-page":"39","volume":"132","author":"O. Johansson","year":"1998","unstructured":"O. Johansson, \u201cClique-decomposition, NLC-decomposition, and modular decomposition-relationships and results for random graphs\u201d Congressus Numerantium 132 (1998) 39\u201360.","journal-title":"Congressus Numerantium"},{"key":"9_CR13","unstructured":"D. Kobler and U. Rotics, \u201cPolynomial algorithms for partitioning problems on graphs with fixed clique-width (Extended Abstract)\u201d Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, (2001) 468\u2013476."},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1142\/S0129054199000241","volume":"10","author":"J.A. Makowsky","year":"1999","unstructured":"J.A. Makowsky and U. Rotics, \u201cOn the classes of graphs with few P4\u2019s\u201d International Journal of Foundations of Computer Science 10 (1999) 329\u2013348.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0166-218X(94)90026-4","volume":"54","author":"E. Wanke","year":"1994","unstructured":"E. Wanke, \u201ck-NLC graphs and polynomial algorithms\u201d Discrete Applied Math. 54 (1994) 251\u2013266.","journal-title":"Discrete Applied Math."}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45477-2_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T13:04:31Z","timestamp":1578488671000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45477-2_9"}},"subtitle":["(Extended abstract)"],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540427070","9783540454779"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-45477-2_9","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"2 October 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}