{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T14:13:04Z","timestamp":1726409584474},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319449524"},{"type":"electronic","value":"9783319449531"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44953-1_27","type":"book-chapter","created":{"date-parts":[[2016,8,22]],"date-time":"2016-08-22T11:12:23Z","timestamp":1471864343000},"page":"421-437","source":"Crossref","is-referenced-by-count":0,"title":["The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors"],"prefix":"10.1007","author":[{"given":"Timon","family":"Hertli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Isabelle","family":"Hurbain","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Millius","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robin A.","family":"Moser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominik","family":"Scheder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"May","family":"Szedl\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,23]]},"reference":[{"key":"27_CR1","unstructured":"Allender, E., Chen, S., Lou, T., Papakonstantinou, P.A., Tang, B.: Width parameterized SAT: time-space tradeoffs. Theory of Computing (to appear)"},{"issue":"2","key":"27_CR2","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/j.jalgor.2004.06.008","volume":"54","author":"R Beigel","year":"2005","unstructured":"Beigel, R., Eppstein, D.: 3-coloring in time $$O(1.3289^n)$$ . J. Algorithms 54(2), 168\u2013204 (2005)","journal-title":"J. Algorithms"},{"key":"27_CR3","series-title":"Frontiers in Artificial Intelligence and Applications","volume-title":"Handbook of Satisfiability","year":"2009","unstructured":"Biere, A., Heule, M.J.H., van Maaren, H., Walsh, T. (eds.): Handbook of Satisfiability. Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press, Amsterdam (2009)"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21\u201324, October 2006Berkeley, California, USA, Proceedings, pp. 575\u2013582. IEEE Computer Society (2006)","DOI":"10.1109\/FOCS.2006.41"},{"issue":"2","key":"27_CR5","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"},{"issue":"1","key":"27_CR6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/BF01651330","volume":"22","author":"CM Fortuin","year":"1971","unstructured":"Fortuin, C.M., Kasteleyn, P.W., Ginibre, J.: Correlation inequalities on some partially ordered sets. Comm. Math. Phys. 22, 89\u2013103 (1971)","journal-title":"Comm. Math. Phys."},{"key":"27_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1007\/11821069_5","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M Grohe","year":"2006","unstructured":"Grohe, M.: The structure of tractable constraint satisfaction problems. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 58\u201372. Springer, Heidelberg (2006)"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proceedings of the seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp. 289\u2013298. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109590"},{"issue":"2","key":"27_CR10","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/120868177","volume":"43","author":"T Hertli","year":"2014","unstructured":"Hertli, T.: 3-SAT faster and simpler - unique-SAT bounds for PPSZ hold in general. SIAM J. Comput. 43(2), 718\u2013729 (2014)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"27_CR11","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. System Sci. 63(4), 512\u2013530 (2001). Special issue on FOCS 1998 (Palo Alto, CA)","journal-title":"J. Comput. System Sci."},{"key":"27_CR12","series-title":"NATO Science Series II: Mathematics, Physics and Chemistry","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/1-4020-3817-8_8","volume-title":"Structural Theory of Automata, Semigroups, and Universal Algebra","author":"A Krokhin","year":"2005","unstructured":"Krokhin, A., Bulatov, A., Jeavons, P.: The complexity of constraint satisfaction: an algebraic approach. In: Kudryavtsev, V.B., Rosenberg, I.G., Goldstein, M. (eds.) Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Mathematics, Physics and Chemistry, vol. 207, pp. 181\u2013213. Springer, Netherlands (2005)"},{"key":"27_CR13","unstructured":"Li, L., Li, X., Liu, T., Xu, K.: From k-SAT to k-CSP: Two generalized algorithms. CoRR, abs\/0801.3147 (2008)"},{"issue":"3","key":"27_CR14","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1145\/1066100.1066101","volume":"52","author":"R Paturi","year":"2005","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M.E., Zane, F.: An improved exponential-time algorithm for $$k$$ -SAT. J. ACM 52(3), 337\u2013364 (2005). (electronic)","journal-title":"J. ACM"},{"key":"27_CR15","unstructured":"Paturi, R., Pudl\u00e1k, P., Zane, F.: Satisfiability coding lemma. Chicago J. Theoret. Comput. Sci., Article 11, 19 (electronic) (1999)"},{"key":"27_CR16","unstructured":"Scheder, D.: PPZ for more than two truth values - an algorithm for constraint satisfaction problems. CoRR, abs\/1010.5717 (2010)"},{"key":"27_CR17","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: A probabilistic algorithm for k-sat and constraint satisfaction problems. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17\u201318 October 1999, New York, pp. 410\u2013414. IEEE Computer Society (1999)","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1007\/978-3-540-24605-3_15","volume-title":"Theory and Applications of Satisfiability Testing","author":"S Szeider","year":"2004","unstructured":"Szeider, S.: On fixed-parameter tractable parameterizations of SAT. In: Giunchiglia, E., Tacchella, A. (eds.) SAT 2003. LNCS, vol. 2919, pp. 188\u2013202. Springer, Heidelberg (2004)"},{"key":"27_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/978-3-540-79723-4_18","volume-title":"Parameterized and Exact Computation","author":"P Traxler","year":"2008","unstructured":"Traxler, P.: The time complexity of constraint satisfaction. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 190\u2013201. Springer, Heidelberg (2008)"},{"key":"27_CR20","unstructured":"Welzl, E.: Boolean Satisfiability - Combinatorics and Algorithms (Lecture Notes) (2005). www.inf.ethz.ch\/~emo\/SmallPieces\/SAT.ps"}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44953-1_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,24]],"date-time":"2017-06-24T17:07:52Z","timestamp":1498324072000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44953-1_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319449524","9783319449531"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44953-1_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}