{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T04:05:32Z","timestamp":1746331532471,"version":"3.40.4"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319092836"},{"type":"electronic","value":"9783319092843"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09284-3_4","type":"book-chapter","created":{"date-parts":[[2014,7,2]],"date-time":"2014-07-02T09:43:21Z","timestamp":1404294201000},"page":"32-47","source":"Crossref","is-referenced-by-count":2,"title":["Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction"],"prefix":"10.1007","author":[{"given":"Takayuki","family":"Sakai","sequence":"first","affiliation":[]},{"given":"Kazuhisa","family":"Seto","sequence":"additional","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"4_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Algorithms and Computations","author":"N. Bansal","year":"1999","unstructured":"Bansal, N., Raman, V.: Upper bounds for MaxSAT: Further improved. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol.\u00a01741, pp. 247\u2013258. Springer, Heidelberg (1999)"},{"issue":"4","key":"4_CR2","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1016\/j.jda.2010.06.001","volume":"8","author":"D. Binkele-Raible","year":"2010","unstructured":"Binkele-Raible, D., Fernau, H.: A new upper bound for Max-2-SAT: A graph-theoretic approach. J. Discrete Algorithms\u00a08(4), 388\u2013401 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-33293-7_6","volume-title":"Parameterized and Exact Computation","author":"I. Bliznets","year":"2012","unstructured":"Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: Thilikos, D.M., Woeginger, G.J. (eds.) IPEC 2012. LNCS, vol.\u00a07535, pp. 37\u201348. Springer, Heidelberg (2012)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: A duality between clause width and clause density for SAT. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC), pp. 252\u2013260 (2006)","DOI":"10.1109\/CCC.2006.6"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C. Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol.\u00a05917, pp. 75\u201385. Springer, Heidelberg (2009)"},{"issue":"1-3","key":"4_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/j.dam.2003.03.002","volume":"142","author":"J. Chen","year":"2004","unstructured":"Chen, J., Kanj, I.A.: Improved exact algorithms for MAX-SAT. Discrete Applied Mathematics\u00a0142(1-3), 17\u201327 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Chen, R., Kabanets, V., Kolokolova, A., Shaltiel, R., Zuckerman, D.: Mining circuit lower bound proofs for meta-algorithms. Electronic Colloquium on Computational Complexity (ECCC) TR13-057 (2013)","DOI":"10.1109\/CCC.2014.34"},{"key":"4_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/11814948_26","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"E. Dantsin","year":"2006","unstructured":"Dantsin, E., Wolpert, A.: AX-SAT for formulas with constant clause density can be solved faster than in O(2 n ) time. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 266\u2013276. Springer, Heidelberg (2006)"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/j.jcss.2011.05.010","volume":"78","author":"S. Gaspers","year":"2012","unstructured":"Gaspers, S., Sorkin, G.B.: A universally fastest algorithm for Max 2-SAT, Max 2-CSP, and everything in between. J. Comput. Syst. Sci.\u00a078(1), 305\u2013335 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"4_CR10","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J. Gramm","year":"2003","unstructured":"Gramm, J., Hirsch, E.A., Niedermeier, R., Rossmanith, P.: Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT. Discrete Applied Mathematics\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-46521-9_15","volume-title":"Algorithms and Complexity","author":"J. Gramm","year":"2000","unstructured":"Gramm, J., Niedermeier, R.: Faster exact solutions for MAX2SAT. In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol.\u00a01767, pp. 174\u2013186. Springer, Heidelberg (2000)"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-3-642-30891-8_14","volume-title":"The Multivariate Algorithmic Revolution and Beyond","author":"G. Gutin","year":"2012","unstructured":"Gutin, G., Yeo, A.: Constraint satisfaction problems parameterized above or below tight bounds: A survey. In: Bodlaender, H.L., Downey, R., Fomin, F.V., Marx, D. (eds.) Fellows Festschrift 2012. LNCS, vol.\u00a07370, pp. 257\u2013286. Springer, Heidelberg (2012)"},{"issue":"1","key":"4_CR13","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1137\/S0097539794261556","volume":"27","author":"J. H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J.: The shrinkage exponent of De Morgan formulas is 2. SIAM J. Comput.\u00a027(1), 48\u201364 (1998)","journal-title":"SIAM J. Comput."},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/3-540-46541-3_5","volume-title":"STACS 2000","author":"E.A. Hirsch","year":"2000","unstructured":"Hirsch, E.A.: A new algorithm for MAX-2-SAT. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 65\u201373. Springer, Heidelberg (2000)"},{"issue":"2","key":"4_CR15","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0166-218X(02)00404-3","volume":"130","author":"E.A. Hirsch","year":"2003","unstructured":"Hirsch, E.A.: Worst-case study of local search for MAX-k-SAT. Discrete Applied Mathematics\u00a0130(2), 173\u2013184 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"4_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E. Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM\u00a021(2), 277\u2013292 (1974)","journal-title":"J. ACM"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Matthews, W., Paturi, R.: A satisfiability algorithm for AC0. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 961\u2013972 (2012)","DOI":"10.1137\/1.9781611973099.77"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Paturi, R., Schneider, S.: A satisfiability algorithm for sparse depth two threshold circuits. In: Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 479\u2013488 (2013)","DOI":"10.1109\/FOCS.2013.58"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1007\/11549345_49","volume-title":"Mathematical Foundations of Computer Science 2005","author":"J. Kneis","year":"2005","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: On the parameterized complexity of exact satisfiability problems. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 568\u2013579. Springer, Heidelberg (2005)"},{"issue":"1","key":"4_CR20","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1137\/080715482","volume":"23","author":"J. Kneis","year":"2009","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: A bound on the pathwidth of sparse graphs with applications to exact algorithms. SIAM J. Discrete Math.\u00a023(1), 407\u2013427 (2009)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"4_CR21","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/j.ipl.2005.11.013","volume":"98","author":"M. Koivisto","year":"2006","unstructured":"Koivisto, M.: Optimal 2-constraint satisfaction via sum-product algorithms. Inf. Process. Lett.\u00a098(1), 24\u201328 (2006)","journal-title":"Inf. Process. Lett."},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Kojevnikov, A., Kulikov, A.S.: A new approach to proving upper bounds for MAX-2-SAT. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 11\u201317 (2006)","DOI":"10.1145\/1109557.1109559"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/11499107_35","volume-title":"Theory and Applications of Satisfiability Testing","author":"A.S. Kulikov","year":"2005","unstructured":"Kulikov, A.S.: Automated generation of simplification rules for SAT and MAXSAT. In: Bacchus, F., Walsh, T. (eds.) SAT 2005. LNCS, vol.\u00a03569, pp. 430\u2013436. Springer, Heidelberg (2005)"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-74510-5_21","volume-title":"Computer Science \u2013 Theory and Applications","author":"A.S. Kulikov","year":"2007","unstructured":"Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR 2007. LNCS, vol.\u00a04649, pp. 194\u2013204. Springer, Heidelberg (2007)"},{"issue":"2","key":"4_CR25","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"Mahajan, M., Raman, V.: Parameterizing above guaranteed values: MaxSAT and MaxCUT. J. Algorithms\u00a031(2), 335\u2013354 (1999)","journal-title":"J. Algorithms"},{"issue":"1","key":"4_CR26","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R. Niedermeier","year":"2000","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for maximum satisfiability. J. Algorithms\u00a036(1), 63\u201388 (2000)","journal-title":"J. Algorithms"},{"key":"4_CR27","doi-asserted-by":"crossref","unstructured":"Santhanam, R.: Fighting perebor: New and improved algorithms for formula and QBF satisfiability. In: Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 183\u2013192 (2010)","DOI":"10.1109\/FOCS.2010.25"},{"issue":"1","key":"4_CR28","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.jalgor.2004.04.012","volume":"54","author":"R. Schuler","year":"2005","unstructured":"Schuler, R.: An algorithm for the satisfiability problem of formulas in conjunctive normal form. J. Algorithms\u00a054(1), 40\u201344 (2005)","journal-title":"J. Algorithms"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1007\/978-3-540-45198-3_32","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A.D. Scott","year":"2003","unstructured":"Scott, A.D., Sorkin, G.B.: Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 382\u2013395. Springer, Heidelberg (2003)"},{"issue":"3-4","key":"4_CR30","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/j.disopt.2007.08.001","volume":"4","author":"A.D. Scott","year":"2007","unstructured":"Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discrete Optimization\u00a04(3-4), 260\u2013287 (2007)","journal-title":"Discrete Optimization"},{"issue":"2","key":"4_CR31","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00037-013-0067-7","volume":"22","author":"K. Seto","year":"2013","unstructured":"Seto, K., Tamaki, S.: A satisfiability algorithm and average-case hardness for formulas over the full binary basis. Computational Complexity\u00a022(2), 245\u2013274 (2013)","journal-title":"Computational Complexity"},{"issue":"2-3","key":"4_CR32","doi-asserted-by":"publisher","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.\u00a0348(2-3), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Williams, R.: Non-uniform ACC circuit lower bounds. In: Proceedings of the 26th Annual IEEE Conference on Computational Complexity (CCC), pp. 115\u2013125 (2011)","DOI":"10.1109\/CCC.2011.36"}],"container-title":["Lecture Notes in Computer Science","Theory and Applications of Satisfiability Testing \u2013 SAT 2014"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09284-3_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T16:52:10Z","timestamp":1746291130000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09284-3_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319092836","9783319092843"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09284-3_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}