{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:49:28Z","timestamp":1766065768911,"version":"3.33.0"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2007,12,14]],"date-time":"2007-12-14T00:00:00Z","timestamp":1197590400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,10]]},"DOI":"10.1007\/s00453-007-9149-8","type":"journal-article","created":{"date-parts":[[2007,12,13]],"date-time":"2007-12-13T17:59:08Z","timestamp":1197568748000},"page":"226-249","source":"Crossref","is-referenced-by-count":43,"title":["Exact Algorithms for Exact Satisfiability and Number of Perfect Matchings"],"prefix":"10.1007","volume":"52","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thore","family":"Husfeldt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,12,14]]},"reference":[{"key":"9149_CR1","series-title":"Lecture Notes in Artificial Intelligence","first-page":"44","volume-title":"Recent Advances in Constraints","author":"O. Angelsmark","year":"2005","unstructured":"Angelsmark, O., Thapper, J.: Partitioning based algorithms for some colouring problems. In: Recent Advances in Constraints. Lecture Notes in Artificial Intelligence, vol. 3978, pp. 44\u201358. Springer, Berlin (2005)"},{"issue":"4","key":"9149_CR2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0020-0190(93)90033-6","volume":"47","author":"E.T. Bax","year":"1993","unstructured":"Bax, E.T.: Inclusion and exclusion algorithm for the Hamiltonian Path problem. Inf. Process. Lett. 47(4), 203\u2013207 (1993)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T. Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput., to appear. Prelim. versions in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA, 21\u201324 October 2006, pp.\u00a0575\u2013582, 583\u2013590. IEEE Computer Society, Los Alamitos, CA (2006)","key":"9149_CR3","DOI":"10.1109\/FOCS.2006.41"},{"doi-asserted-by":"crossref","unstructured":"Bodlaender, H., Kratsch, D.: An exact algorithm for graph coloring with polynomial memory. Technical report UU-CS-2006-015, Utrecht University (2006)","key":"9149_CR4","DOI":"10.1007\/11841036_60"},{"key":"9149_CR5","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1016\/j.orl.2004.03.002","volume":"32","author":"J.M. Byskov","year":"2004","unstructured":"Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547\u2013556 (2004)","journal-title":"Oper. Res. Lett."},{"unstructured":"Byskov, J.M.: Exact algorithms for graph colouring and exact satisfiability. Ph.D. thesis, University of Aarhus (2004)","key":"9149_CR6"},{"issue":"1\u20133","key":"9149_CR7","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."},{"unstructured":"Chien, S.: A determinant-based algorithm for counting perfect matchings in a general graph. In: Proc. 15th SODA, pp. 728\u2013735 (2004)","key":"9149_CR8"},{"key":"9149_CR9","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1093\/comjnl\/14.1.38","volume":"14","author":"N. Christofides","year":"1971","unstructured":"Christofides, N.: An algorithm for the chromatic number of a graph. Comput. J. 14, 38\u201339 (1971)","journal-title":"Comput. J."},{"issue":"3","key":"9149_CR10","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9149_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, New York (1999). ISBN 0-387-94883-X"},{"issue":"2\u20133","key":"9149_CR12","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 exact satisfiability. Theor. Comput. Sci. 320(2\u20133), 373\u2013394 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"7","key":"9149_CR13","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theorem proving. Commun. ACM 5(7), 394\u2013397 (1962)","journal-title":"Commun. ACM"},{"issue":"2","key":"9149_CR14","doi-asserted-by":"crossref","first-page":"131","DOI":"10.7155\/jgaa.00064","volume":"7","author":"D. Eppstein","year":"2003","unstructured":"Eppstein, D.: Small maximal independent sets and faster exact graph coloring. J. Graph Algorithms Appl. 7(2), 131\u2013140 (2003)","journal-title":"J. Graph Algorithms Appl."},{"unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. In: Bull. EATCS, vol.\u00a087 (2005)","key":"9149_CR15"},{"doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination\u2014a case study. In: Proceedings of the 32nd ICALP, pp. 191\u2013203 (2005)","key":"9149_CR16","DOI":"10.1007\/11523468_16"},{"issue":"5","key":"9149_CR17","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.ipl.2005.10.012","volume":"97","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., H\u00f6ie, K.: Pathwidth of cubic graphs and exact algorithms. Inf. Process. Lett. 97(5), 191\u2013196 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9149_CR18","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/S0196-6774(02)00224-9","volume":"45","author":"T. Feder","year":"2002","unstructured":"Feder, T., Motwani, R.: Worst-case time bounds for coloring and satisfiability problems. J. Algorithms 45(2), 192\u2013201 (2002)","journal-title":"J. Algorithms"},{"unstructured":"Feige, U., Kilian, J.: Exponential time algorithms for computing the bandwidth of a graph. Manuscript. Cited in [38]","key":"9149_CR19"},{"issue":"3","key":"9149_CR20","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM J. Comput. 16(3), 486\u2013502 (1987)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9149_CR21","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1137\/0406022","volume":"6","author":"M. Hujter","year":"1993","unstructured":"Hujter, M., Tuza, Z.: On the number of maximal independent sets in triangle-free graphs. SIAM J. Discrete Math. 6(2), 284\u2013288 (1993)","journal-title":"SIAM J. Discrete Math."},{"doi-asserted-by":"crossref","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In: Proc. 33rd STOC, pp. 712\u2013721 (2001)","key":"9149_CR22","DOI":"10.1145\/380752.380877"},{"key":"9149_CR23","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0167-6377(82)90044-X","volume":"1","author":"R.M. Karp","year":"1982","unstructured":"Karp, R.M.: Dynamic programming meets the principle of inclusion-exclusion. Oper. Res. Lett. 1,\u00a049\u201351 (1982)","journal-title":"Oper. Res. Lett."},{"key":"9149_CR24","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/800179.810218","volume-title":"ACM \u201977: Proceedings of the 1977 annual conference","author":"S. Kohn","year":"1977","unstructured":"Kohn, S., Gottlieb, A., Kohn, M.: A generating function approach to the Traveling Salesman Problem. In: ACM \u201977: Proceedings of the 1977 annual conference, pp. 294\u2013300. ACM Press, New York (1977)"},{"doi-asserted-by":"crossref","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Algorithms based on the treewidth of sparse graphs. In: Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 385\u2013396 (2005)","key":"9149_CR25","DOI":"10.1007\/11604686_34"},{"issue":"3","key":"9149_CR26","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"E.L. Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66\u201367 (1976)","journal-title":"Inf. Process. Lett."},{"key":"9149_CR27","volume-title":"Matching Theory","author":"L. Lov\u00e1sz","year":"1986","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory. North-Holland, Amsterdam (1986)"},{"issue":"1","key":"9149_CR28","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."},{"doi-asserted-by":"crossref","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. (1965)","key":"9149_CR29","DOI":"10.1007\/BF02760024"},{"key":"9149_CR30","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."},{"doi-asserted-by":"crossref","unstructured":"Porschen, S.: On some weighted satisfiability and graph problems. In: Proc. 31st SOFSEM. Lecture Notes in Computer Science, vol. 3381, pp. 278\u2013287 (2005)","key":"9149_CR31","DOI":"10.1007\/978-3-540-30577-4_31"},{"key":"9149_CR32","series-title":"Carus Math. Monographs","doi-asserted-by":"crossref","DOI":"10.5948\/UPO9781614440147","volume-title":"Combinatorial Mathematics","author":"H.J. Ryser","year":"1963","unstructured":"Ryser, H.J.: Combinatorial Mathematics. Carus Math. Monographs, no.\u00a014. Math. Assoc. of America, Washington, DC (1963)"},{"issue":"3","key":"9149_CR33","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S. Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9149_CR34","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"32","author":"S.P. Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graps. SIAM J. Comput. 32(2), 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"key":"9149_CR35","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theor. Comput. Sci. 8, 189\u2013201 (1979)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"9149_CR36","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R. Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(1\u20132), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9149_CR37","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/3-540-36478-1_17","volume-title":"Combinatorial Optimization: Eureka, You Shrink!","author":"G.J. Woeginger","year":"2003","unstructured":"Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization: Eureka, You Shrink!, pp.\u00a0185\u2013207. Springer, Berlin (2003)"},{"doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems. In: Proc. 1st IWPEC. Lecture Notes in Computer Science, vol. 3162, pp. 281\u2013290 (2004)","key":"9149_CR38","DOI":"10.1007\/978-3-540-28639-4_25"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9149-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9149-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9149-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T17:44:22Z","timestamp":1737654262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9149-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,14]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2008,10]]}},"alternative-id":["9149"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9149-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,12,14]]}}}