{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T18:16:49Z","timestamp":1725733009642},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642390708"},{"type":"electronic","value":"9783642390715"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39071-5_24","type":"book-chapter","created":{"date-parts":[[2013,6,24]],"date-time":"2013-06-24T01:23:17Z","timestamp":1372036997000},"page":"318-334","source":"Crossref","is-referenced-by-count":5,"title":["A SAT Approach to Clique-Width"],"prefix":"10.1007","author":[{"given":"Marijn J. H.","family":"Heule","sequence":"first","affiliation":[]},{"given":"Stefan","family":"Szeider","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","first-page":"399","volume-title":"Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI 2009","author":"G. Audemard","year":"2009","unstructured":"Audemard, G., Simon, L.: Predicting learnt clauses quality in modern sat solvers. In: Proceedings of the 21st International Jont Conference on Artifical Intelligence, IJCAI 2009, pp. 399\u2013404. Morgan Kaufmann Publishers Inc., San Francisco (2009)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1007\/978-3-642-36046-6_9","volume-title":"Mathematical and Engineering Methods in Computer Science","author":"M. Bey\u00df","year":"2013","unstructured":"Bey\u00df, M.: Fast algorithm for rank-width. In: Ku\u010dera, A., Henzinger, T.A., Ne\u0161et\u0159il, J., Vojnar, T., Anto\u0161, D. (eds.) MEMICS 2012. LNCS, vol.\u00a07721, pp. 82\u201393. Springer, Heidelberg (2013)"},{"key":"24_CR3","unstructured":"Biere, A.: Lingeling and friends entering the SAT Challenge 2012. In: Balint, A., Belov, A., Diepold, A., Gerber, S., J\u00e4rvisalo, M., Sinz, C. (eds.) Solver and Benchmark Descriptions. Department of Computer Science Series of Publications B, vol.\u00a0B-2012-2, pp. 33\u201334. University of Helsinki (2012)"},{"issue":"39","key":"24_CR4","doi-asserted-by":"publisher","first-page":"5187","DOI":"10.1016\/j.tcs.2011.05.022","volume":"412","author":"B.-M. Bui-Xuan","year":"2011","unstructured":"Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean-width of graphs. Theoretical Computer Science\u00a0412(39), 5187\u20135204 (2011)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"24_CR5","doi-asserted-by":"publisher","first-page":"834","DOI":"10.1016\/j.dam.2011.03.020","volume":"160","author":"D.G. Corneil","year":"2012","unstructured":"Corneil, D.G., Habib, M., Lanlignel, J.-M., Reed, B., Rotics, U.: Polynomial-time recognition of clique-width \u2264\u20093 graphs. Discr. Appl. Math.\u00a0160(6), 834\u2013865 (2012)","journal-title":"Discr. Appl. Math."},{"issue":"4","key":"24_CR6","doi-asserted-by":"publisher","first-page":"825","DOI":"10.1137\/S0097539701385351","volume":"34","author":"D.G. Corneil","year":"2005","unstructured":"Corneil, D.G., Rotics, U.: On the relationship between clique-width and treewidth. SIAM J. Comput.\u00a034(4), 825\u2013847 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"24_CR7","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s002249910009","volume":"33","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst.\u00a033(2), 125\u2013150 (2000)","journal-title":"Theory Comput. Syst."},{"issue":"1-2","key":"24_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0166-218X(00)00221-3","volume":"108","author":"B. Courcelle","year":"2001","unstructured":"Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discr. Appl. Math.\u00a0108(1-2), 23\u201352 (2001)","journal-title":"Discr. Appl. Math."},{"issue":"1-3","key":"24_CR9","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"Courcelle, B., Olariu, S.: Upper bounds to the clique-width of graphs. Discr. Appl. Math.\u00a0101(1-3), 77\u2013114 (2000)","journal-title":"Discr. Appl. Math."},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/BFb0017394","volume-title":"Graph Grammars and Their Application to Computer Science","author":"B. Courcelle","year":"1991","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Context-free handle-rewriting hypergraph grammars. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol.\u00a0532, pp. 253\u2013268. Springer, Heidelberg (1991)"},{"issue":"2","key":"24_CR11","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"Courcelle, B., Engelfriet, J., Rozenberg, G.: Handle-rewriting hypergraph grammars. J. of Computer and System Sciences\u00a046(2), 218\u2013270 (1993)","journal-title":"J. of Computer and System Sciences"},{"issue":"2","key":"24_CR12","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s00224-009-9211-9","volume":"47","author":"B. Courcelle","year":"2010","unstructured":"Courcelle, B., Twigg, A.: Constrained-path labellings on graphs of bounded clique-width. Theory Comput. Syst.\u00a047(2), 531\u2013567 (2010)","journal-title":"Theory Comput. Syst."},{"key":"24_CR13","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol.\u00a0173. Springer, New York (2000)","edition":"2"},{"key":"24_CR14","unstructured":"Alex Dow, P., Korf, R.E.: Best-first search for treewidth. In: Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada, July 22-26, pp. 1146\u20131151. AAAI Press (2007)"},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"502","DOI":"10.1007\/978-3-540-24605-3_37","volume-title":"Theory and Applications of Satisfiability Testing","author":"N. E\u00e9n","year":"2004","unstructured":"E\u00e9n, N., S\u00f6rensson, N.: An extensible SAT-solver. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol.\u00a02919, pp. 502\u2013518. Springer, Heidelberg (2004)"},{"issue":"2","key":"24_CR16","doi-asserted-by":"publisher","first-page":"909","DOI":"10.1137\/070687256","volume":"23","author":"M.R. Fellows","year":"2009","unstructured":"Fellows, M.R., Rosamond, F.A., Rotics, U., Szeider, S.: Clique-width is NP-complete. SIAM J. Discrete Math.\u00a023(2), 909\u2013939 (2009)","journal-title":"SIAM J. Discrete Math."},{"key":"24_CR17","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-540-72200-7_23","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"M. Gebser","year":"2007","unstructured":"Gebser, M., Kaufmann, B., Neumann, A., Schaub, T.: clasp: A conflict-driven answer set solver. In: Baral, C., Brewka, G., Schlipf, J. (eds.) LPNMR 2007. LNCS (LNAI), vol.\u00a04483, pp. 260\u2013265. Springer, Heidelberg (2007)"},{"key":"24_CR18","unstructured":"Gent, I.P.: Arc consistency in SAT. In: van Harmelen, F. (ed.) 15th European Conference on Artificial Intelligence (ECAI 2002), pp. 121\u2013125. IOS Press (2002)"},{"key":"24_CR19","unstructured":"Gogate, V., Dechter, R.: A complete anytime algorithm for treewidth. In: Proceedings of the Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI 2004), Arlington, Virginia, pp. 201\u2013208. AUAI Press (2004)"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/3-540-46784-X_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M.C. Golumbic","year":"1999","unstructured":"Golumbic, M.C., Rotics, U.: On the clique-width of perfect graph classes extended abstract. Internat. J. Found. Comput. Sci. 11(3), 423\u2013443 (2000); Selected papers from In: Widmayer, P., Neyer, G., Eidenbenz, S. (eds.) WG 1999. LNCS, vol.\u00a01665, pp. 135\u2013443. Springer, Heidelberg (1999)"},{"issue":"1","key":"24_CR21","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.cosrev.2010.01.001","volume":"4","author":"M. Habib","year":"2010","unstructured":"Habib, M., Paul, C.: A survey of the algorithmic aspects of modular decomposition. Computer Science Review\u00a04(1), 41\u201359 (2010)","journal-title":"Computer Science Review"},{"issue":"6","key":"24_CR22","doi-asserted-by":"publisher","first-page":"888","DOI":"10.1016\/j.dam.2011.03.018","volume":"160","author":"P. Heggernes","year":"2012","unstructured":"Heggernes, P., Meister, D., Papadopoulos, C.: Characterising the linear clique-width of a class of graphs by forbidden induced subgraphs. Discr. Appl. Math.\u00a0160(6), 888\u2013901 (2012)","journal-title":"Discr. Appl. Math."},{"key":"24_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/978-3-642-20712-9_18","volume-title":"Computer Science \u2013 Theory and Applications","author":"P. Heggernes","year":"2011","unstructured":"Heggernes, P., Meister, D., Rotics, U.: Computing the clique-width of large path powers in linear time via a new characterisation of clique-width. In: Kulikov, A., Vereshchagin, N. (eds.) CSR 2011. LNCS, vol.\u00a06651, pp. 233\u2013246. Springer, Heidelberg (2011)"},{"key":"24_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-642-28050-4_18","volume-title":"Parameterized and Exact Computation","author":"E.M. Hvidevold","year":"2012","unstructured":"Hvidevold, E.M., Sharmin, S., Telle, J.A., Vatshelle, M.: Finding good decompositions for dynamic programming on dense graphs. In: Marx, D., Rossmanith, P. (eds.) IPEC 2011. LNCS, vol.\u00a07112, pp. 219\u2013231. Springer, Heidelberg (2012)"},{"key":"24_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-642-28717-6_20","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"H. Katebi","year":"2012","unstructured":"Katebi, H., Sakallah, K.A., Markov, I.L.: Conflict anticipation in the search for graph automorphisms. In: Bj\u00f8rner, N., Voronkov, A. (eds.) LPAR-18 2012. LNCS, vol.\u00a07180, pp. 243\u2013257. Springer, Heidelberg (2012)"},{"key":"24_CR26","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/S1571-0653(05)80078-2","volume":"8","author":"A.M.C.A. Koster","year":"2001","unstructured":"Koster, A.M.C.A., Bodlaender, H.L., van Hoesel, S.P.M.: Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics\u00a08, 54\u201357 (2001)","journal-title":"Electronic Notes in Discrete Mathematics"},{"issue":"3","key":"24_CR27","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1002\/jgt.20620","volume":"70","author":"C. Lee","year":"2012","unstructured":"Lee, C., Lee, J., Oum, S.-I.: Rank-width of random graphs. J. Graph Theory\u00a070(3), 339\u2013347 (2012)","journal-title":"J. Graph Theory"},{"key":"24_CR28","unstructured":"McKay, B.D.: Practical graph isomorphism. In: Proceedings of the Tenth Manitoba Conference on Numerical Mathematics and Computing, Vol. I (Winnipeg, Man., 1980), Winnipeg, Man, vol.\u00a030, pp. 45\u201387 (1981)"},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Oum, S.-I.: Approximating rank-width and clique-width quickly. ACM Transactions on Algorithms\u00a05(1) (2008)","DOI":"10.1145\/1435375.1435385"},{"issue":"4","key":"24_CR30","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","volume":"96","author":"S.-I. Oum","year":"2006","unstructured":"Oum, S.-I., Seymour, P.: Approximating clique-width and branch-width. J. Combin. Theory Ser. B\u00a096(4), 514\u2013528 (2006)","journal-title":"J. Combin. Theory Ser. B"},{"key":"24_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-02777-2_6","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2009","author":"M. Samer","year":"2009","unstructured":"Samer, M., Veith, H.: Encoding treewidth into SAT. In: Kullmann, O. (ed.) SAT 2009. LNCS, vol.\u00a05584, pp. 45\u201350. Springer, Heidelberg (2009)"},{"key":"24_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1007\/11564751_73","volume-title":"Principles and Practice of Constraint Programming - CP 2005","author":"C. Sinz","year":"2005","unstructured":"Sinz, C.: Towards an optimal CNF encoding of boolean cardinality constraints. In: van Beek, P. (ed.) CP 2005. LNCS, vol.\u00a03709, pp. 827\u2013831. Springer, Heidelberg (2005)"},{"issue":"3","key":"24_CR33","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1007\/s10589-011-9397-z","volume":"51","author":"J. Cole Smith","year":"2012","unstructured":"Cole Smith, J., Ulusal, E., Hicks, I.V.: A combinatorial optimization algorithm for solving the branchwidth problem. Comput. Optim. Appl.\u00a051(3), 1211\u20131229 (2012)","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"24_CR34","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/s10601-008-9061-0","volume":"14","author":"N. Tamura","year":"2009","unstructured":"Tamura, N., Taga, A., Kitagawa, S., Banbara, M.: Compiling finite linear CSP into SAT. Constraints\u00a014(2), 254\u2013272 (2009)","journal-title":"Constraints"},{"key":"24_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/3-540-45349-0_32","volume-title":"Principles and Practice of Constraint Programming - CP 2000","author":"T. Walsh","year":"2000","unstructured":"Walsh, T.: SAT v CSP. In: Dechter, R. (ed.) CP 2000. LNCS, vol.\u00a01894, pp. 441\u2013456. Springer, Heidelberg (2000)"},{"key":"24_CR36","doi-asserted-by":"crossref","unstructured":"Wanke, E.: k-NLC graphs and polynomial algorithms. Discr. Appl. Math. 54(2-3), 251\u2013266 (1994); Efficient algorithms and partial k-trees","DOI":"10.1016\/0166-218X(94)90026-4"},{"key":"24_CR37","unstructured":"Weisstein, E.: MathWorld online mathematics resource, \n                      \n                        mathworld.wolfram.com"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39071-5_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T13:58:36Z","timestamp":1557842316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-39071-5_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642390708","9783642390715"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39071-5_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}