{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T19:57:02Z","timestamp":1725566222260},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540230717"},{"type":"electronic","value":"9783540286394"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-28639-4_22","type":"book-chapter","created":{"date-parts":[[2010,9,20]],"date-time":"2010-09-20T20:25:35Z","timestamp":1285014335000},"page":"248-259","source":"Crossref","is-referenced-by-count":4,"title":["Automated Proofs of Upper Bounds on the Running Time of Splitting Algorithms"],"prefix":"10.1007","author":[{"given":"Sergey S.","family":"Fedin","sequence":"first","affiliation":[]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"22_CR1","doi-asserted-by":"crossref","unstructured":"Byskov, J.M., Madsen, B.A., Skjernaa, B.: New Algorithms for Exact Satisfiability. Theoretical Computer Science Preprint (2003)","DOI":"10.7146\/brics.v10i30.21798"},{"key":"22_CR2","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)"},{"key":"22_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-45995-2_32","volume-title":"LATIN 2002: Theoretical Informatics","author":"J. Chen","year":"2002","unstructured":"Chen, J., Kanj, I.: Improved exact algorithms for MAX-SAT. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol.\u00a02286, pp. 341\u2013355. Springer, Heidelberg (2002)"},{"key":"22_CR4","unstructured":"Dantsin, E., Hirsch, E.A., Ivanov, S., Vsemirnov, M.: Algorithms for SAT and Upper Bounds on Their Complexity. ECCC Technical Report 01-012 (2001), Electronic address: ftp:\/\/ftp.eccc.unitrier.de\/pub\/eccc\/reports\/2001\/TR01-012\/index.html , A Russian version appears in Zapiski Nauchnykh Seminarov POMI, 277, pp. 14\u201346 (2001)"},{"key":"22_CR5","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/368273.368557","volume":"5","author":"M. Davis","year":"1962","unstructured":"Davis, M., Logemann, G., Loveland, D.: A machine program for theoremproving. Comm. ACM\u00a05, 394\u2013397 (1962)","journal-title":"Comm. ACM"},{"key":"22_CR6","first-page":"129","volume":"293","author":"S.S. Fedin","year":"2002","unstructured":"Fedin, S.S., Kulikov, A.S.: A 2|E|\/4-time Algorithm for MAX-CUT. Zapiski nauchnykh seminarov POMI\u00a0293, 129\u2013138 (2002), English translation is to appear in Journal of Mathematical Sciences","journal-title":"Zapiski nauchnykh seminarov POMI"},{"key":"22_CR7","doi-asserted-by":"crossref","unstructured":"Gramm, J., Guo, J., H\u00fcffner, F., Niedermeier, R.: Automated Generation of Search Tree Algorithms for Hard GraphModification Problems. In: Proceedings of 11th Annual European Symposium on Algorithms, pp. 642\u2013653 (2003)","DOI":"10.1007\/978-3-540-39658-1_58"},{"issue":"2","key":"22_CR8","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.: New worstcase upper bounds for MAX-2-SAT with application to MAX-CUT. Discrete Applied Mathematics\u00a0130(2), 139\u2013155 (2003)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"22_CR9","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1023\/A:1006340920104","volume":"24","author":"E.A. Hirsch","year":"2000","unstructured":"Hirsch, E.A.: New worst-case upper bounds for SAT. Journal of Automated Reasoning\u00a024(4), 397\u2013420 (2000)","journal-title":"Journal of Automated Reasoning"},{"key":"22_CR10","first-page":"118","volume":"293","author":"A.S. Kulikov","year":"2002","unstructured":"Kulikov, A.S.: An upper bound O(20.16254n) for Exact 3-Satisfiability: A simpler proof. Zapiski nauchnykh seminarov POMI\u00a0293, 118\u2013128 (2002), English translation is to appear in Journal of Mathematical Sciences","journal-title":"Zapiski nauchnykh seminarov POMI"},{"key":"22_CR11","unstructured":"Kullmann, O., Luckhardt, H.: Algorithms for SAT\/TAUT decision based on various measures. Informatics and Computation (1998)"},{"key":"22_CR12","unstructured":"Nikolenko, S.I., Sirotkin, A.V.: Worst-case upper bounds for SAT: automated proof. In: Proceedings of the Eight ESSLI Student Session, pp. 225\u2013232 (2003), Available from http:\/\/logic.pdmi.ras.ru\/~sergey"},{"key":"22_CR13","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., Srinivasa Rao, S.: A Simplified NP-complete MAXSAT Problem. Information Processing Letters\u00a065, 1\u20136 (1998)","journal-title":"Information Processing Letters"}],"container-title":["Lecture Notes in Computer Science","Parameterized and Exact Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-28639-4_22.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:26:46Z","timestamp":1605760006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-28639-4_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230717","9783540286394"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-28639-4_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}