{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T12:05:12Z","timestamp":1709813112352},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2005,8,1]],"date-time":"2005-08-01T00:00:00Z","timestamp":1122854400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2005,8]]},"DOI":"10.1007\/s10472-005-7036-z","type":"journal-article","created":{"date-parts":[[2005,9,15]],"date-time":"2005-09-15T07:41:11Z","timestamp":1126770071000},"page":"419-436","source":"Crossref","is-referenced-by-count":12,"title":["Improving exact algorithms for MAX-2-SAT"],"prefix":"10.1007","volume":"44","author":[{"given":"Haiou","family":"Shen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hantao","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"17036_CR1","unstructured":"T. Alsinet, F. Many\u00e0 and J. Planes, Improved branch and bound algorithms for Max-SAT, in: Proc. of 6th International Conference on the Theory and Applications of Satisfiability Testing, SAT2003 (2003) pp. 408\u2013415."},{"key":"17036_CR2","unstructured":"T. Alsinet, F. Many\u00e0 and J. Planes, Improved branch and bound algorithms for Max-2-SAT and Weighted Max-2-SAT, in: Catalonian Conference on Artificial Intelligence (2003)."},{"issue":"3","key":"17036_CR3","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"B. Aspvall, M.F. Plass and R.E. Tarjan, A linear-time algorithm for testing the truth of certain quantified Boolean formulas, Information Processing Letters 8(3) (1979) 121\u2013123.","journal-title":"Information Processing Letters"},{"key":"17036_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Proc. of the 10th Annual Conference on Algorithms and Computation, ISSAC\u201999","author":"N. Bansal","year":"1999","unstructured":"N. Bansal and V. Raman, Upper bounds for MaxSat: Further improved, in: Proc. of the 10th Annual Conference on Algorithms and Computation, ISSAC\u201999, eds. Aggarwal and Rangan, Lecture Notes in Computer Science, Vol. 1741 (Springer, New York, 1999) pp. 247\u2013258."},{"issue":"4","key":"17036_CR5","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1009725216438","volume":"2","author":"B. Borchers","year":"1999","unstructured":"B. Borchers and J. Furman, A two-phase exact algorithm for MAX-SAT and weighted MAX-SAT problems, Journal of Combinatorial Optimization 2(4) (1999) 299\u2013306.","journal-title":"Journal of Combinatorial Optimization"},{"key":"17036_CR6","unstructured":"R.J. Bayardo and J.D. Pehoushek, Counting models using connected components, in: 17th National Conference on Artificial Intelligence (AAAI) (2000) pp. 157\u2013162."},{"key":"17036_CR7","first-page":"395","volume-title":"Discrete Mathematics and Theoretical Computer Science","author":"J. Cheriyan","year":"1996","unstructured":"J. Cheriyan, W.H. Cunningnham, L. Tuncel and Y. Wang, A linear programming and rounding approach to Max 2-Sat, in: Discrete Mathematics and Theoretical Computer Science, Vol. 26 (Science Press, New York, 1996) pp. 395\u2013414."},{"issue":"1","key":"17036_CR8","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0304-3975(01)00174-8","volume":"289","author":"E. Dantsin","year":"2002","unstructured":"E. Dantsin, A. Goerdt, E.A. Hirsch, R. Kannan, J. Kleinberg, C. Papadimitriou, P. Raghavan and U. Sch\u00f6ning, A deterministic (2\u22122\/(k+1))n algorithm for k-SAT based on local search, Theoretical Computer Science 289(1) (2002) 69\u201383.","journal-title":"Theoretical Computer Science"},{"key":"17036_CR9","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","volume":"7","author":"M. Davis","year":"1962","unstructured":"M. Davis, G. Logemann and D. Loveland, A machine program for theorem-proving, Communications of the Association for Computing Machinery 7 (1962) 394\u2013397.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"17036_CR10","first-page":"17","volume":"5","author":"P. Erd\u00f6s","year":"1960","unstructured":"P. Erd\u00f6s and A. Rnyi, On the evolution of random graphs, Mat. Kutato Int. Kozl. 5 (1960) 17\u201361.","journal-title":"Mat. Kutato Int. Kozl."},{"key":"17036_CR11","unstructured":"J. Gramm, Exact algorithms for Max2Sat and their applications, Diplomarbeit, Universit\u00e4t T\u00fcbingen (1999)."},{"key":"17036_CR12","doi-asserted-by":"crossref","unstructured":"S. Givry, J. Larrosa, P. Meseguer and T. Schiex, Solving Max-SAT as weighted CSP, in: Principles and Practice of Constraint Programming \u2013 9th International Conference CP 2003, Kinsale, Ireland (September 2003).","DOI":"10.1007\/978-3-540-45193-8_25"},{"issue":"2","key":"17036_CR13","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/S0166-218X(02)00402-X","volume":"130","author":"J. Gramm","year":"2003","unstructured":"J. Gramm, E.A. Hirsch, R. Niedermeier and P. Rossmanith, Worst-case upper bounds for MAX-2-SAT with application to MAX-CUT, Discrete Applied Mathematics 130(2) (2003) 139\u2013155.","journal-title":"Discrete Applied Mathematics"},{"key":"17036_CR14","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF02241270","volume":"44","author":"P. Hansen","year":"1990","unstructured":"P. Hansen and B. Jaumard, Algorithms for the maximum satisfiability problem, Computing 44 (1990) 279\u2013303.","journal-title":"Computing"},{"key":"17036_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-46541-3_5","volume-title":"Proc. of the 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000","author":"E.A. Hirsch","year":"2000","unstructured":"E.A. Hirsch, A new algorithm for MAX-2-SAT, in: Proc. of the 17th International Symposium on Theoretical Aspects of Computer Science, STACS 2000, Lecture Notes in Computer Science, Vol. 1770 (Springer, New York, 2000) pp. 65\u201373."},{"issue":"4","key":"17036_CR16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1023\/A:1006340920104","volume":"24","author":"E.A. Hirsch","year":"2000","unstructured":"E.A. Hirsch, New worst-case upper bounds for SAT, Journal of Automated Reasoning 24(4) (2000) 397\u2013420.","journal-title":"Journal of Automated Reasoning"},{"key":"17036_CR17","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","volume":"31","author":"M. Mahajan","year":"1999","unstructured":"M. Mahajan and V. Raman, Parameterizing above guaranteed values: Max-Sat and Max-Cut, Journal of Algorithms 31 (1999) 335\u2013354.","journal-title":"Journal of Algorithms"},{"key":"17036_CR18","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1006\/jagm.2000.1075","volume":"36","author":"R. Niedermeier","year":"2000","unstructured":"R. Niedermeier and P. Rossmanith, New upper bounds for maximum satisfiability, Journal of Algorithms 36 (2000) 63\u201388.","journal-title":"Journal of Algorithms"},{"key":"17036_CR19","doi-asserted-by":"crossref","unstructured":"H. Shen and H. Zhang, An empirical study of Max-2-Sat phase transitions, in: Proc. of LICS\u201903 Workshop on Typical Case Complexity and Phase Transitions, Ottawa, Canada (June 2003).","DOI":"10.1016\/S1571-0653(04)00464-0"},{"key":"17036_CR20","doi-asserted-by":"crossref","unstructured":"H. Shen and H. Zhang, Improving Exact Algorithms for MAX-2-SAT, in: Proc. of 8th International Symposium on Artificial Intelligence and Mathematics (2004).","DOI":"10.1007\/s10472-005-7036-z"},{"key":"17036_CR21","unstructured":"H. Shen and H. Zhang, Study of Lower Bound Functions for MAX-2-SAT, in: Proc. of the 19th National Conf. on Artificial Intelligence (AAAI), San Jose, CA (July 2004)."},{"key":"17036_CR22","doi-asserted-by":"crossref","unstructured":"R. Wallace and E. Freuder, Comparative studies of constraint satisfaction and Davis\u2013Putnam algorithms for maximum satisfiability problems, in: Cliques, Coloring and Satisfiability, eds.D. Johnson and M. Trick (1996) pp. 587\u2013615.","DOI":"10.1090\/dimacs\/026\/28"},{"key":"17036_CR23","doi-asserted-by":"crossref","unstructured":"H. Xu, R.A. Rutenbar and K. Sakallah, Sub-SAT: A formulation for related Boolean satisfiability with applications in routing, in: ISPD\u201902, San Diego, CA (April 2002).","DOI":"10.1145\/505388.505432"},{"key":"17036_CR24","doi-asserted-by":"crossref","unstructured":"H. Zhang, H. Shen and F. Many\u00e0, Exact algorithms for MAX-SAT, in: Proc. of International Workshop on First-Order Theorem Proving (FTP 2003).","DOI":"10.1016\/S1571-0661(04)80663-7"},{"key":"17036_CR25","unstructured":"X. Zhao and W. Zhang, An efficient algorithm for maximum Boolean satisfiability based on unit propagation, linear programming, and dynamic weighting, Preprint, Department of Computer Science, Washington University (2004)."}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-7036-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10472-005-7036-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-005-7036-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T13:58:11Z","timestamp":1586440691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10472-005-7036-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,8]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,8]]}},"alternative-id":["17036"],"URL":"https:\/\/doi.org\/10.1007\/s10472-005-7036-z","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"value":"1012-2443","type":"print"},{"value":"1573-7470","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,8]]}}}