{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:17:15Z","timestamp":1759637835198},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T00:00:00Z","timestamp":1419292800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s00224-014-9600-6","type":"journal-article","created":{"date-parts":[[2014,12,22]],"date-time":"2014-12-22T02:16:44Z","timestamp":1419214604000},"page":"426-443","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Solving Sparse Instances of Max SAT via Width Reduction and Greedy Restriction"],"prefix":"10.1007","volume":"57","author":[{"given":"Takayuki","family":"Sakai","sequence":"first","affiliation":[]},{"given":"Kazuhisa","family":"Seto","sequence":"additional","affiliation":[]},{"given":"Suguru","family":"Tamaki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,23]]},"reference":[{"key":"9600_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Raman, V.: Upper bounds for MaxSAT: Further improved. In: Proceedings of the 10th International Symposium on Algorithms and Computation (ISAAC), Lecture Notes in Computer Science, vol. 1741, pp 247\u2013258. Springer (1999)","DOI":"10.1007\/3-540-46632-0_26"},{"issue":"4","key":"9600_CR2","doi-asserted-by":"crossref","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. Discret. Algorithm. 8(4), 388\u2013401 (2010)","journal-title":"J. Discret. Algorithm."},{"key":"9600_CR3","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC), Lecture Notes in Computer Science, vol. 7535, pp 37\u201348. Springer (2012)","DOI":"10.1007\/978-3-642-33293-7_6"},{"key":"9600_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":"9600_CR5","doi-asserted-by":"crossref","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Revised Selected Papers from the 4th International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, vol. 5917, pp 75\u201385 (2009)","DOI":"10.1007\/978-3-642-11269-0_6"},{"issue":"1-3","key":"9600_CR6","doi-asserted-by":"crossref","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. Discret. Appl. Math. 142(1-3), 17\u201327 (2004)","journal-title":"Discret. Appl. Math."},{"key":"9600_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). Also. In: Proceedings of the 29th Annual IEEE Conference on Computational Complexity (CCC), pp. 262\u2013273 (2014)","DOI":"10.1109\/CCC.2014.34"},{"key":"9600_CR8","doi-asserted-by":"crossref","unstructured":"Dantsin, E., Wolpert, A.: MAX-SAT for formulas with constant clause density can be solved faster than in O(2 n ) time. In: Proceedings of the 9th International Conference on Theory and Applications of Satisfiability Testing (SAT), Lecture Notes in Computer Science, vol. 4121, pp 266\u2013276. Springer (2006)","DOI":"10.1007\/11814948_26"},{"issue":"1","key":"9600_CR9","doi-asserted-by":"crossref","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. 78(1), 305\u2013335 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9600_CR10","doi-asserted-by":"crossref","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. Discret. Appl. Math. 130(2), 139\u2013155 (2003)","journal-title":"Discret. Appl. Math."},{"key":"9600_CR11","doi-asserted-by":"crossref","unstructured":"Gramm, J., Niedermeier, R.: Faster exact solutions for MAX2SAT. In: Proceedings of the 4th Italian Conference on Algorithms and Complexity (CIAC), Lecture Notes in Computer Science, vol. 1767, pp 174\u2013186. Springer (2000)","DOI":"10.1007\/3-540-46521-9_15"},{"key":"9600_CR12","doi-asserted-by":"crossref","unstructured":"Gutin, G., Yeo, A.: Constraint satisfaction problems parameterized above or below tight bounds: A survey. In: The Multivariate Algorithmic Revolution and Beyond, Lecture Notes in Computer Science, vol. 7370, pp 257\u2013286. Springer (2012)","DOI":"10.1007\/978-3-642-30891-8_14"},{"issue":"1","key":"9600_CR13","first-page":"48","volume":"27","author":"J H\u00e5stad","year":"1998","unstructured":"H\u00e5stad, J.: The shrinkage exponent of De Morgan formulas is 2. SIAM. J. Comput. 27(1), 48\u201364 (1998)","journal-title":"J. Comput."},{"key":"9600_CR14","doi-asserted-by":"crossref","unstructured":"Hirsch, E.A.: A new algorithm for MAX-2-SAT. In: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, vol. 1770, pp 65\u201373. Springer (2000)","DOI":"10.1007\/3-540-46541-3_5"},{"issue":"2","key":"9600_CR15","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0166-218X(02)00404-3","volume":"130","author":"EA Hirsch","year":"2003","unstructured":"Hirsch, E.A.: Worst-case study of local search for MAX-k-SAT. Discret. Appl. Math. 130(2), 173\u2013184 (2003)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"9600_CR16","doi-asserted-by":"crossref","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 21(2), 277\u2013292 (1974)","journal-title":"J. ACM"},{"key":"9600_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":"9600_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":"9600_CR19","doi-asserted-by":"crossref","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: On the parameterized complexity of exact satisfiability problems. In: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science (MFCS), Lecture Notes in Computer Science, vol. 3618, pp 568\u2013579. Springer (2005)","DOI":"10.1007\/11549345_49"},{"issue":"1","key":"9600_CR20","doi-asserted-by":"crossref","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. Discret. Math 23(1), 407\u2013427 (2009)","journal-title":"J. Discret. Math"},{"issue":"1","key":"9600_CR21","doi-asserted-by":"crossref","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. 98(1), 24\u201328 (2006)","journal-title":"Inf. Process. Lett."},{"key":"9600_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":"9600_CR23","doi-asserted-by":"crossref","unstructured":"Kulikov, A.S.: Automated generation of simplification rules for SAT and MAXSAT. In: Proceedings of the 8th International Conference on Theory and Applications of Satisfiability Testing (SAT), Lecture Notes in Computer Science, vol. 3569, pp 430\u2013436. Springer (2005)","DOI":"10.1007\/11499107_35"},{"key":"9600_CR24","doi-asserted-by":"crossref","unstructured":"Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: Proceedings of the 8th International Computer Science Symposium in Russia (CSR), Lecture Notes in Computer Science, vol. 4649, pp 194\u2013204. Springer (2007)","DOI":"10.1007\/978-3-540-74510-5_21"},{"issue":"2","key":"9600_CR25","doi-asserted-by":"crossref","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. Algorithm. 31(2), 335\u2013354 (1999)","journal-title":"J. Algorithm."},{"issue":"1","key":"9600_CR26","doi-asserted-by":"crossref","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. Algorithm. 36(1), 63\u201388 (2000)","journal-title":"J. Algorithm."},{"key":"9600_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":"9600_CR28","doi-asserted-by":"crossref","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. Algorithm. 54(1), 40\u201344 (2005)","journal-title":"J. Algorithm."},{"key":"9600_CR29","doi-asserted-by":"crossref","unstructured":"Scott, A.D., Sorkin, G.B.: Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances. In: Proceedings of the 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) and the 7th International Workshop on Randomization and Computation (RANDOM), Lecture Notes in Computer Science, vol. 2764, pp 382\u2013395. Springer (2003)","DOI":"10.1007\/978-3-540-45198-3_32"},{"issue":"3-4","key":"9600_CR30","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1016\/j.disopt.2007.08.001","volume":"4","author":"AD Scott","year":"2007","unstructured":"Scott, A.D., Sorkin, G.B.: Linear-programming design and analysis of fast algorithms for Max 2-CSP. Discret. Optim. 4(3-4), 260\u2013287 (2007)","journal-title":"Discret. Optim."},{"issue":"2","key":"9600_CR31","doi-asserted-by":"crossref","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. Comput. Complex. 22(2), 245\u2013274 (2013)","journal-title":"Comput. Complex."},{"issue":"2-3","key":"9600_CR32","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(2-3), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9600_CR33","doi-asserted-by":"crossref","unstructured":"Williams, R.: Nonuniform ACC circuit lower bounds. J. ACM 61(1, 2), 1\u201332 (2014)","DOI":"10.1145\/2559903"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9600-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9600-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9600-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T17:36:26Z","timestamp":1566149786000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9600-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,23]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["9600"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9600-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,23]]}}}