{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T12:07:25Z","timestamp":1759666045732},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,5]]},"DOI":"10.1007\/s00224-012-9412-5","type":"journal-article","created":{"date-parts":[[2012,5,14]],"date-time":"2012-05-14T06:35:44Z","timestamp":1336977344000},"page":"687-718","source":"Crossref","is-referenced-by-count":25,"title":["Partition Into Triangles on Bounded Degree Graphs"],"prefix":"10.1007","volume":"52","author":[{"given":"Johan M. M.","family":"van Rooij","sequence":"first","affiliation":[]},{"given":"Marcel E.","family":"van Kooten\u00a0Niekerk","sequence":"additional","affiliation":[]},{"given":"Hans L.","family":"Bodlaender","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,5,15]]},"reference":[{"key":"9412_CR1","first-page":"856","volume-title":"10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999","author":"R. Beigel","year":"1999","unstructured":"Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: 10th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1999, pp. 856\u2013857. Society for Industrial and Applied Mathematics, Philadelphia (1999)"},{"key":"9412_CR2","series-title":"Leibniz International Proceedings in Informatics","first-page":"95","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010","author":"A. Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A.: Exact covers via determinants. In: Marion, J.-Y., Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010. Leibniz International Proceedings in Informatics, vol. 3, pp. 95\u2013106. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Leibniz (2010)"},{"issue":"2","key":"9412_CR3","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1007\/s00453-007-9149-8","volume":"52","author":"A. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Exact algorithms for exact satisfiability and number of perfect matchings. Algorithmica 52(2), 226\u2013249 (2008)","journal-title":"Algorithmica"},{"issue":"2","key":"9412_CR4","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Comput. 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9412_CR5","first-page":"382","volume":"62","author":"N. Bourgeois","year":"2010","unstructured":"Bourgeois, N., Escoffier, B., Paschos, V.Th., van Rooij, J.M.M.: Fast algorithms for max independent set. Algorithmica 62(1\u20132), 382\u2013415 (2010)","journal-title":"Algorithmica"},{"issue":"1\u20133","key":"9412_CR6","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1016\/j.tcs.2004.12.023","volume":"332","author":"J.M. Byskov","year":"2005","unstructured":"Byskov, J.M., Madsen, B.A., Skjernaa, B.: New algorithms for exact satisfiability. Theor. Comput. Sci. 332(1\u20133), 515\u2013541 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"2\u20133","key":"9412_CR7","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/j.tcs.2004.02.035","volume":"320","author":"V. Dahll\u00f6f","year":"2004","unstructured":"Dahll\u00f6f, V., Jonsson, P., Beigel, R.: Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320(2\u20133), 373\u2013394 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9412_CR8","doi-asserted-by":"crossref","first-page":"473","DOI":"10.1016\/S0304-3975(01)00257-2","volume":"287","author":"L. Drori","year":"2002","unstructured":"Drori, L., Peleg, D.: Faster exact solutions for some NP-hard problems. Theor. Comput. Sci. 287(2), 473\u2013499 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9412_CR9","series-title":"Texts in Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact Exponential Algorithms","author":"F.V. Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Berlin (2010)"},{"key":"9412_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)"},{"issue":"2","key":"9412_CR11","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9412_CR12","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R. Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9412_CR13","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V. Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inf. Process. Lett. 37(1), 27\u201335 (1991)","journal-title":"Inf. Process. Lett."},{"key":"9412_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1007\/978-3-642-11269-0_21","volume-title":"4th International Workshop on Parameterized and Exact Computation, IWPEC 2009","author":"M. Koivisto","year":"2009","unstructured":"Koivisto, M.: Partitioning into sets of bounded cardinality. In: Chen, J., Fomin, F.V. (eds.) 4th International Workshop on Parameterized and Exact Computation, IWPEC 2009. Lecture Notes in Computer Science, vol. 5917, pp. 258\u2013263. Springer, Berlin (2009)"},{"key":"9412_CR15","first-page":"118","volume":"293","author":"A.S. Kulikov","year":"2002","unstructured":"Kulikov, A.S.: An upper bound O(20.16254n ) for exact 3-satisfiability: a simpler proof. Zap. Nauchn. Semin. POMI 293, 118\u2013128 (2002). English translation: J. Math. Sci. 293, 1995\u20131999 (2005)","journal-title":"Zap. Nauchn. Semin. POMI"},{"key":"9412_CR16","unstructured":"Kullmann, O., Luckhardt, H.: Deciding propositional tautologies: algorithms and their complexity. Technical report, Fachbereich Mathematik, Johann Wolfgang Goethe-Universit\u00e4t, Frankfurt, Germany (1997)"},{"key":"9412_CR17","unstructured":"Lipton, R.J.: Fast Exponential Algorithms. Weblog: G\u00f6del\u2019s Lost Letter and P=NP, February 13 (2009). http:\/\/rjlipton.wordpress.com\/2009\/02\/13\/polynomial-vs-exponential-time"},{"issue":"1","key":"9412_CR18","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.ipl.2005.08.011","volume":"97","author":"B.A. Madsen","year":"2006","unstructured":"Madsen, B.A.: An algorithm for exact satisfiability analysed with the number of clauses as parameter. Inf. Process. Lett. 97(1), 28\u201330 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9412_CR19","first-page":"419","volume":"43","author":"B. Monien","year":"1981","unstructured":"Monien, B., Speckenmeyer, E., Vornberger, O.: Upper bounds for covering problems. Methods Oper. Res. 43, 419\u2013431 (1981)","journal-title":"Methods Oper. Res."},{"issue":"1","key":"9412_CR20","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1007\/s10472-005-0428-2","volume":"43","author":"S. Porschen","year":"2005","unstructured":"Porschen, S., Randerath, B., Speckenmeyer, E.: Exact 3-satisfiability is decidable in time O(20.16254n ). Ann. Math. Artif. Intell. 43(1), 173\u2013193 (2005)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9412_CR21","first-page":"216","volume-title":"10th Annual ACM Symposium on Theory of Computing, STOC 1978","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: 10th Annual ACM Symposium on Theory of Computing, STOC 1978, pp. 216\u2013226. ACM, New York (1978)"},{"issue":"3","key":"9412_CR22","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1137\/0210033","volume":"10","author":"R. Schroeppel","year":"1981","unstructured":"Schroeppel, R., Shamir, A.: A T=O(2 n\/2), S=O(2 n\/4) algorithm for certain NP-complete problems. SIAM J. Comput. 10(3), 456\u2013464 (1981)","journal-title":"SIAM J. Comput."},{"key":"9412_CR23","unstructured":"Wahlstr\u00f6m, M.: Algorithms, measures, and upper bounds for satisfiability and related problems. PhD thesis, Department of Computer and Information Science, Link\u00f6ping University, Link\u00f6ping, Sweden (2007)"},{"key":"9412_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"5th International Workshop on Combinatorial Optimization\u2014Eureka, You Shrink","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) 5th International Workshop on Combinatorial Optimization\u2014Eureka, You Shrink! Lecture Notes in Computer Science, vol. 2570, pp. 185\u2013208. Springer, Berlin (2003)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9412-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T18:41:30Z","timestamp":1497984090000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9412-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,5,15]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,5]]}},"alternative-id":["9412"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9412-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,5,15]]}}}