{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:28:56Z","timestamp":1773815336770,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T00:00:00Z","timestamp":1644364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61872048"],"award-info":[{"award-number":["61872048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672536"],"award-info":[{"award-number":["61672536"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61702557"],"award-info":[{"award-number":["61702557"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s00453-022-00938-8","type":"journal-article","created":{"date-parts":[[2022,2,9]],"date-time":"2022-02-09T08:02:58Z","timestamp":1644393778000},"page":"982-1006","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A Refined Branching Algorithm for the Maximum Satisfiability Problem"],"prefix":"10.1007","volume":"84","author":[{"given":"Wenjun","family":"Li","sequence":"first","affiliation":[]},{"given":"Chao","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7731-6818","authenticated-orcid":false,"given":"Yongjie","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Jianer","family":"Chen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1516-0480","authenticated-orcid":false,"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,9]]},"reference":[{"key":"938_CR1","doi-asserted-by":"crossref","unstructured":"Bansal, N., Raman, V.: Upper bounds for MaxSAT: further improved. In: ISAAC, pp. 247\u2013258 (1999)","DOI":"10.1007\/3-540-46632-0_26"},{"key":"938_CR2","unstructured":"Biere, A., Heule, M., van Maaren, H., Walsh, T. (eds.): Handbook of satisfiability. In: Frontiers in Artificial Intelligence and Applications, vol. 185. IOS Press (2009)"},{"key":"938_CR3","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Golovnev, A.: A new algorithm for parameterized MAX-SAT. In: IPEC, pp. 37\u201348 (2012)","DOI":"10.1007\/978-3-642-33293-7_6"},{"issue":"1","key":"938_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10958-012-1101-z","volume":"188","author":"IA Bliznets","year":"2013","unstructured":"Bliznets, I.A.: A new upper bound for $$(n, 3)$$-MAX-SAT. J. Math. Sci. 188(1), 1\u20136 (2013)","journal-title":"J. Math. Sci."},{"key":"938_CR5","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L.: Kernelization: New upper and lower bound techniques. In: IWPEC, pp. 17\u201337 (2009)","DOI":"10.1007\/978-3-642-11269-0_2"},{"key":"938_CR6","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1613\/jair.4480","volume":"51","author":"S Cai","year":"2014","unstructured":"Cai, S., Luo, C., Su, K.: Scoring functions based on second level score for $$k$$-SAT with long clauses. J. Artif. Intell. Res. 51, 413\u2013441 (2014)","journal-title":"J. Artif. Intell. Res."},{"issue":"1\u20133","key":"938_CR7","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 Appl. Math. 142(1\u20133), 17\u201327 (2004)","journal-title":"Discrete Appl. Math."},{"issue":"40\u201342","key":"938_CR8","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"938_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.tcs.2017.01.020","volume":"670","author":"J Chen","year":"2017","unstructured":"Chen, J., Xu, C., Wang, J.: Dealing with $$4$$-variables by resolution: an improved MaxSAT algorithm. Theor. Comput. Sci. 670, 33\u201344 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"938_CR10","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"938_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"issue":"3","key":"938_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"MR Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"938_CR13","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/S0895480192243516","volume":"7","author":"MX Goemans","year":"1994","unstructured":"Goemans, M.X., Williamson, D.P.: New 3\/4-approximation algorithms for the maximum satisfiability problem. SIAM J. Discrete Math. 7(4), 656\u2013666 (1994)","journal-title":"SIAM J. Discrete Math."},{"key":"938_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, S., Roy, S., Saurabh, S., Zehavi, M.: When rigging a tournament, let greediness blind you. In: IJCAI, pp. 275\u2013281 (2018)","DOI":"10.24963\/ijcai.2018\/38"},{"key":"938_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.006","volume":"243","author":"F Hutter","year":"2017","unstructured":"Hutter, F., Lindauer, M., Balint, A., Bayless, S., Hoos, H., Leyton-Brown, K.: The configurable SAT solver challenge (CSSC). Artif. Intell. 243, 1\u201325 (2017)","journal-title":"Artif. Intell."},{"issue":"2","key":"938_CR16","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of $$k$$-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"938_CR17","unstructured":"Kleinberg, J.M., Tardos, \u00c9.: Algorithm design. Addison-Wesley (2006)"},{"key":"938_CR18","doi-asserted-by":"crossref","unstructured":"Kulikov, A.S., Kutzkov, K.: New bounds for MAX-SAT by clause learning. In: CSR, pp. 194\u2013204 (2007)","DOI":"10.1007\/978-3-540-74510-5_21"},{"key":"938_CR19","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1613\/jair.2215","volume":"30","author":"CM Li","year":"2007","unstructured":"Li, C.M., Many\u00e0, F., Planes, J.: New inference rules for Max-SAT. J. Artif. Intell. Res. 30, 321\u2013359 (2007)","journal-title":"J. Artif. Intell. Res."},{"key":"938_CR20","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.artint.2016.11.001","volume":"243","author":"C Luo","year":"2017","unstructured":"Luo, C., Cai, S., Su, K., Huang, W.: CCEHC: An efficient local search algorithm for weighted partial maximum satisfiability. Artif. Intell. 243, 26\u201344 (2017)","journal-title":"Artif. Intell."},{"key":"938_CR21","unstructured":"Majumdar, D., Raman, V., Saurabh, S.: Kernels for structural parameterizations of vertex cover: case of small degree modulators. In: IPEC, pp. 331\u2013342 (2015)"},{"key":"938_CR22","doi-asserted-by":"crossref","unstructured":"Marques-Silva, J.: The impact of branching heuristics in propositional satisfiability algorithms. In: P.\u00a0Barahona, J.J. Alferes (eds.) Progress in Artificial Intelligence, pp. 62\u201374 (1999)","DOI":"10.1007\/3-540-48159-1_5"},{"key":"938_CR23","doi-asserted-by":"crossref","unstructured":"Marques-Silva, J.: Practical applications of Boolean Satisfiability. In: WODES, pp. 74\u201380 (2008)","DOI":"10.1109\/WODES.2008.4605925"},{"key":"938_CR24","doi-asserted-by":"crossref","unstructured":"Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press (2011)","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"issue":"4","key":"938_CR25","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/s10601-013-9146-2","volume":"18","author":"A Morgado","year":"2013","unstructured":"Morgado, A., Heras, F., Liffiton, M.H., Planes, J., Marques-Silva, J.: Iterative and core-guided MaxSAT solving: a survey and assessment. Constraints 18(4), 478\u2013534 (2013)","journal-title":"Constraints"},{"key":"938_CR26","doi-asserted-by":"crossref","unstructured":"Niedermeier, R., Rossmanith, P.: New upper bounds for MaxSat. In: ICALP, pp. 575\u2013584 (1999)","DOI":"10.1007\/3-540-48523-6_54"},{"issue":"1","key":"938_CR27","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 36(1), 63\u201388 (2000)","journal-title":"J. Algorithms"},{"issue":"3","key":"938_CR28","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/15M1053369","volume":"46","author":"M Poloczek","year":"2017","unstructured":"Poloczek, M., Schnitger, G., Williamson, D.P., van Zuylen, A.: Greedy algorithms for the maximum satisfiability problem: simple algorithms and inapproximability bounds. SIAM J. Comput. 46(3), 1029\u20131061 (2017)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"938_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V Raman","year":"1998","unstructured":"Raman, V., Ravikumar, B., Rao, S.S.: A simplified NP-complete MAXSAT problem. Inform. Process. Lett. 65(1), 1\u20136 (1998)","journal-title":"Inform. Process. Lett."},{"key":"938_CR30","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: STOC, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"938_CR31","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.jpdc.2016.12.014","volume":"106","author":"AA Sohanghpurwala","year":"2017","unstructured":"Sohanghpurwala, A.A., Hassan, M.W., Athanas, P.: Hardware accelerated SAT solvers\u2014a survey. J. Parallel Distrib. Comput. 106, 170\u2013184 (2017)","journal-title":"J. Parallel Distrib. Comput."},{"key":"938_CR32","unstructured":"Sturtevant, N.R.: Last-branch and speculative pruning algorithms for Max$${}^{\\text{n}}$$. In: IJCAI, pp. 669\u2013675 (2003)"},{"issue":"1","key":"938_CR33","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s004530010035","volume":"28","author":"L Trevisan","year":"2000","unstructured":"Trevisan, L.: Approximating satisfiable satisfiability problems. Algorithmica 28(1), 145\u2013172 (2000)","journal-title":"Algorithmica"},{"key":"938_CR34","doi-asserted-by":"crossref","unstructured":"Wang, Y., Cai, S., Chen, J., Yin, M.: A fast local search algorithm for minimum weight dominating set problem on massive graphs. In: IJCAI, pp. 1514\u20131522 (2018)","DOI":"10.24963\/ijcai.2018\/210"},{"key":"938_CR35","doi-asserted-by":"crossref","unstructured":"Xu, C., Li, W., Yang, Y., Chen, J., Wang, J.: Resolution and domination: An improved exact MaxSAT algorithm. In: IJCAI, pp. 1191\u20131197 (2019)","DOI":"10.24963\/ijcai.2019\/166"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00938-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00938-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00938-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,16]],"date-time":"2022-03-16T15:09:35Z","timestamp":1647443375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00938-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,9]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["938"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00938-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,9]]},"assertion":[{"value":"29 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}