{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:19:49Z","timestamp":1725560389328},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540287025"},{"type":"electronic","value":"9783540318675"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549345_52","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T14:05:47Z","timestamp":1127829947000},"page":"603-614","source":"Crossref","is-referenced-by-count":0,"title":["An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems"],"prefix":"10.1007","author":[{"given":"Daniel","family":"Kr\u00e1l\u2019","sequence":"first","affiliation":[]},{"given":"Ond\u0159ej","family":"Pangr\u00e1c","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154","volume-title":"The probabilistic method","author":"N. Alon","year":"2000","unstructured":"Alon, N., Spencer, J.: The probabilistic method, 2nd edn. John Wiley, New York (2000)","edition":"2"},{"key":"52_CR2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626371","volume-title":"The discrepancy method: Randomness and complexity","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: The discrepancy method: Randomness and complexity. Cambridge University Press, Cambridge (2000)"},{"doi-asserted-by":"crossref","unstructured":"Cook, S., Mitchell, D.: Finding Hard Instances of the Satisfiability Problem: A Survey. In: Satisfiability Problem: Theory and Applications. DIMACS Series in DMTCS, vol.\u00a035, AMS (1997)","key":"52_CR3","DOI":"10.1090\/dimacs\/035\/01"},{"key":"52_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/978-3-540-27836-8_41","volume-title":"Automata, Languages and Programming","author":"Z. Dvo\u0159\u00e1k","year":"2004","unstructured":"Dvo\u0159\u00e1k, Z., Kr\u00e1l, D., Pangr\u00e1c, O.: Locally consistent constraint satisfaction problems. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 469\u2013480. Springer, Heidelberg (2004)"},{"key":"52_CR5","first-page":"329","volume-title":"Proc. of the 12th ACM-SIAM Symposium on Discrete Algorithms","author":"D. Eppstein","year":"2001","unstructured":"Eppstein, D.: Improved Algorithms for 3-coloring, 3-edge-coloring and Constraint Satisfaction. In: Proc. of the 12th ACM-SIAM Symposium on Discrete Algorithms, pp. 329\u2013337. SIAM, Philadelphia (2001)"},{"issue":"2","key":"52_CR6","doi-asserted-by":"publisher","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\u00a045(2), 192\u2013201 (2002)","journal-title":"J. Algorithms"},{"issue":"4","key":"52_CR7","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of ACM\u00a048(4), 798\u2013859 (2001); A preliminary version appeared. In: Proc. 28th ACM Symposium on Theory of Computing (STOC), pp. 1\u201310. ACM Press, New York (1997)","journal-title":"Journal of ACM"},{"key":"52_CR8","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0304-3975(85)90166-5","volume":"40","author":"M.A. Huang","year":"1985","unstructured":"Huang, M.A., Lieberherr, K.: Implications of Forbidden Structures for Extremal Algorithmic Problems. Theoretical Computer Science\u00a040, 195\u2013210 (1985)","journal-title":"Theoretical Computer Science"},{"key":"52_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04650-0","volume-title":"Extremal Combinatorics with Applications in Computer Science","author":"S. Jukna","year":"2001","unstructured":"Jukna, S.: Extremal Combinatorics with Applications in Computer Science. Springer, Heidelberg (2001)"},{"key":"52_CR10","first-page":"323","volume-title":"Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"D. Kr\u00e1l","year":"2004","unstructured":"Kr\u00e1l, D.: Locally Satisfiable Formulas. In: Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 323\u2013332. SIAM, Philadelphia (2004)"},{"issue":"2","key":"52_CR11","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1145\/322248.322260","volume":"28","author":"K. Lieberherr","year":"1981","unstructured":"Lieberherr, K., Specker, E.: Complexity of Partial Satisfaction. J. of the ACM\u00a028(2), 411\u2013422 (1981)","journal-title":"J. of the ACM"},{"unstructured":"Lieberherr, K., Specker, E.: Complexity of Partial Satisfaction II. Technical Report 293, Dept. of EECS, Princeton University (1982)","key":"52_CR12"},{"key":"52_CR13","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"52_CR14","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1145\/800133.804350","volume-title":"Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC)","author":"T.J. Schaefer","year":"1978","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. of the 10th Annual ACM Symposium on Theory of Computing (STOC), pp. 216\u2013226. ACM Press, New York (1978)"},{"unstructured":"Trevisan, L.: On Local versus Global Satisfiability. SIAM J. Disc. Math. A preliminary version available as ECCC report TR97-12 (to appear)","key":"52_CR15"},{"key":"52_CR16","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1214\/aoms\/1177703585","volume":"35","author":"Z. Usiskin","year":"1963","unstructured":"Usiskin, Z.: Max-min Probabilities in the Voting Paradox. Ann. Math. Stat.\u00a035, 857\u2013862 (1963)","journal-title":"Ann. Math. Stat."},{"key":"52_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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: J\u00fcnger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol.\u00a02570, pp. 185\u2013207. Springer, Heidelberg (2003)"},{"key":"52_CR18","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1006\/jagm.1994.1045","volume":"17","author":"M. Yannakakis","year":"1994","unstructured":"Yannakakis, M.: On the Approximation of Maximum Satisfiability. J. Algorithms\u00a017, 475\u2013502 (1994); A preliminary version appeared. In: Proc. of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1\u20139. SIAM, Philadelphia (1992)","journal-title":"J. Algorithms"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549345_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:58:31Z","timestamp":1619506711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549345_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287025","9783540318675"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11549345_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}