{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:34Z","timestamp":1750308154246,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":30,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132568","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T16:53:01Z","timestamp":1153759981000},"page":"354-362","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Clique-width minimization is NP-hard"],"prefix":"10.1145","author":[{"given":"Michael R.","family":"Fellows","sequence":"first","affiliation":[{"name":"University of Newcastle, Callaghan, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frances A.","family":"Rosamond","sequence":"additional","affiliation":[{"name":"University of Newcastle, Callaghan, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Udi","family":"Rotics","sequence":"additional","affiliation":[{"name":"Netanya Academic College, Netanya, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[{"name":"Durham University, Durham, England, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_1_1_1","DOI":"10.1137\/0608024"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_2_1","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_3_2_1_3_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/3-540-36136-7_5","volume-title":"Algorithms and computation","author":"Boliac R.","year":"2002","unstructured":"R. Boliac and V. Lozin . On the clique-width of graphs in hereditary classes . In Algorithms and computation , volume 2518 of Lecture Notes in Computer Science , pages 44 -- 54 . Springer Verlag , 2002 . R. Boliac and V. Lozin. On the clique-width of graphs in hereditary classes. In Algorithms and computation, volume 2518 of Lecture Notes in Computer Science, pages 44--54. Springer Verlag, 2002."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_4_1","DOI":"10.1007\/s00224-004-1154-6"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.1007\/s00224-005-1199-1"},{"key":"e_1_3_2_1_6_1","volume-title":"4th Latin American Symposium (LATIN 2000","volume":"1776","author":"Corneil D. G.","year":"2000","unstructured":"D. G. Corneil , M. Habib , J.-M. Lanlignel , B. A. Reed , and U. Rotics . Polynomial time recognition of clique-width \u2264 3 graphs (extended abstract). In G. H. Gonnet, D. Panario, and A. Viola, editors, Theoretical Informatics , 4th Latin American Symposium (LATIN 2000 ), volume 1776 of Lecture Notes in Computer Science, pages 126--134 , 2000 . D. G. Corneil, M. Habib, J.-M. Lanlignel, B. A. Reed, and U. Rotics. Polynomial time recognition of clique-width \u2264 3 graphs (extended abstract). In G. H. Gonnet, D. Panario, and A. Viola, editors, Theoretical Informatics, 4th Latin American Symposium (LATIN 2000), volume 1776 of Lecture Notes in Computer Science, pages 126--134, 2000."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.5555\/647682.732486"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_8_1","DOI":"10.1007\/BF01204169"},{"key":"e_1_3_2_1_9_1","series-title":"Lecture Notes in Computer Science","first-page":"253","volume-title":"H. Ehrig, H.-J","author":"Courcelle B.","year":"1990","unstructured":"B. Courcelle , J. Engelfriet , and G. Rozenberg . Context-free handle-rewriting hypergraph grammars . In H. Ehrig, H.-J . Kreowski, and G. Rozenberg, editors, Graph-Grammars and their Application to Computer Science, 4th International Workshop, Bremen, Germany, March 5--9, 1990 , Proceedings , volume 532 of Lecture Notes in Computer Science , pages 253 -- 268 , 1991. B. Courcelle, J. Engelfriet, and G. Rozenberg. Context-free handle-rewriting hypergraph grammars. In H. Ehrig, H.-J. Kreowski, and G. Rozenberg, editors, Graph-Grammars and their Application to Computer Science, 4th International Workshop, Bremen, Germany, March 5--9, 1990, Proceedings, volume 532 of Lecture Notes in Computer Science, pages 253--268, 1991."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_10_1","DOI":"10.1016\/0022-0000(93)90004-G"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1007\/s002249910009"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1016\/S0166-218X(00)00221-3"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_13_1","DOI":"10.1016\/0304-3975(93)90064-Z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_3_2_1_15_1","volume-title":"July","author":"Courcelle B.","year":"2004","unstructured":"B. Courcelle and S. Oum . Vertex-minors, monadic second-order logic and a conjecture by Seese . Submitted, July 2004 . B. Courcelle and S. Oum. Vertex-minors, monadic second-order logic and a conjecture by Seese. Submitted, July 2004."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_16_1","DOI":"10.7155\/jgaa.00065"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_19_1","DOI":"10.1007\/978-3-540-45077-1_8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_20_1","DOI":"10.1007\/978-3-540-39890-5_21"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_21_1","DOI":"10.1007\/11604686_7"},{"key":"e_1_3_2_1_22_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/978-3-540-24698-5_16","volume-title":"LATIN 2004: Theoretical informatics","author":"Gurski F.","year":"2004","unstructured":"F. Gurski and E. Wanke . Vertex disjoint paths on clique-width bounded graphs (extended abstract) . In LATIN 2004: Theoretical informatics , volume 2976 of Lecture Notes in Computer Science , pages 119 -- 128 . Springer Verlag , 2004 . F. Gurski and E. Wanke. Vertex disjoint paths on clique-width bounded graphs (extended abstract). In LATIN 2004: Theoretical informatics, volume 2976 of Lecture Notes in Computer Science, pages 119--128. Springer Verlag, 2004."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_23_1","DOI":"10.1016\/j.tcs.2005.05.018"},{"key":"e_1_3_2_1_24_1","first-page":"39","volume-title":"Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing","volume":"132","year":"1998","unstructured":"\u00d6. Johansson. Clique-decomposition, NLC-decomposition , and modular decomposition---relationships and results for random graphs . In Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing ( Boca Raton, FL , 1998 ), volume 132 of Congr. Numer., pages 39 -- 60 , 1998. \u00d6. Johansson. Clique-decomposition, NLC-decomposition, and modular decomposition---relationships and results for random graphs. In Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998), volume 132 of Congr. Numer., pages 39--60, 1998."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_26_1","DOI":"10.1016\/0020-0190(92)90234-M"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_27_1","DOI":"10.1016\/S0166-218X(02)00198-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1016\/j.disc.2004.02.008"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_29_1","DOI":"10.1137\/S0895480102419755"},{"key":"e_1_3_2_1_30_1","volume-title":"Oct.","author":"Oum S.","year":"2004","unstructured":"S. Oum and P. Seymour . Approximating clique-width and branch-width . Submitted, Oct. 2004 . S. Oum and P. Seymour. Approximating clique-width and branch-width. Submitted, Oct. 2004."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_31_1","DOI":"10.1016\/0168-0072(91)90054-P"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_32_1","DOI":"10.1016\/S0012-365X(03)00295-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_33_1","DOI":"10.1016\/0166-218X(94)90026-4"}],"event":{"sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC06","name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA"},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132568","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132568","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:50Z","timestamp":1750263530000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132568"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":30,"alternative-id":["10.1145\/1132516.1132568","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132568","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}