{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:31Z","timestamp":1759638091297},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540669166"},{"type":"electronic","value":"9783540466321"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46632-0_26","type":"book-chapter","created":{"date-parts":[[2007,11,24]],"date-time":"2007-11-24T19:45:01Z","timestamp":1195933501000},"page":"247-258","source":"Crossref","is-referenced-by-count":36,"title":["Upper Bounds for MaxSat: Further Improved"],"prefix":"10.1007","author":[{"given":"Nikhil","family":"Bansal","sequence":"first","affiliation":[]},{"given":"Venkatesh","family":"Raman","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"issue":"3","key":"26_CR1","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"R. Balasubramanian, M. R. Fellows and V. Raman, \u2018An Improved fixed parameter algorithm for vertex cover\u2019 Information Processing Letters, 65 (3):163\u2013168, 1998.","journal-title":"Information Processing Letters"},{"key":"26_CR2","unstructured":"N. Bansal and V. Raman, \u2018Upper Bounds for MaxSat: Further Improved\u2019, Technical Report of the Institute of Mathematical Sciences, IMSc preprint 99\/08\/30."},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"R. Beigel and D. Eppstein, \u20183-coloring in time O(1:3446n): A no-MIS Algorithm\u2019, In Proc of IEEE Foundations of Computer Science (1995) 444\u2013452.","DOI":"10.1109\/SFCS.1995.492575"},{"key":"26_CR4","unstructured":"E. Dantsin, M. R. Gavrilovich E. A. Hirsch and B. Konev, \u2018Approximation algorithms for MAX SAT: a better performance ratio at the cost of a longer running time\u2019, PDMI preprint 14\/1998, Stekolov Institute of Mathematics at St. Petersburg, 1998."},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, November 1998.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"26_CR6","unstructured":"E.A. Hirsch, \u2018Two new upper bounds for SAT\u2019, Proc. of 9th Symposium on Discrete Algorithms, (1998) 521\u2013530."},{"key":"26_CR7","unstructured":"O. Kullmann, \u2018Worst-case analysis, 3-SAT decision and lower bounds: approaches for improved SAT algorithms`, DIMACS Proc. SAT Workshop 1996, AMS, 1996."},{"key":"26_CR8","unstructured":"M. Mahajan and V. Raman, \u2018Parameterizing above guaranteed values: MaxSat and MaxCut\u2019. Technical Report TR97-033, ECCC Trier, 1997. To appear in Journal of Algorithms."},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"B. Monien, E. Speckenmeyer, \u2018Solving Satisfiability in less than 2n steps\u2019, Discrete Applied Mathematics, 10 (1985) 287\u2013295.","DOI":"10.1016\/0166-218X(85)90050-2"},{"key":"26_CR10","series-title":"Lect Notes Comput Sci","volume-title":"Symposum on Thoretical Aspects of Computer Science (STACS)","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith, \u2018Upper bounds for Vertex Cover: Further Improved\u2019. in Symposum on Thoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Springer Verlag. March (1999)."},{"key":"26_CR11","series-title":"Lect Notes Comput Sci","volume-title":"International Colloquium on Automata, Languages and Programming (ICALP)","author":"R. Niedermeier","year":"1999","unstructured":"R. Niedermeier and P. Rossmanith, \u2018New Upper Bounds for MAXSAT\u2019, International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, Springer Verlag (1999)."},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"R. Paturi, P. Pudlak, M. Saks, and F. Zane. \u2018An improved exponential-time algorithm for k-SAT\u2019, In Proc. of 39th IEEE Foundations of Computer Science (1998).","DOI":"10.1109\/SFCS.1998.743513"},{"key":"26_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BFb0055762","volume-title":"Proc. of 23rd Conference on Mathematical Foundations of Computer Science","author":"P. Pudlak","year":"1998","unstructured":"P. Pudlak, \u2018Satisfiability-algorithms and logic\u2019, In Proc. of 23rd Conference on Mathematical Foundations of Computer Science, 1450 in Lecture Notes in Computer Science Springer Verlag, August (1998) 129\u2013141."},{"key":"26_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0020-0190(97)00223-8","volume":"65","author":"V. Raman","year":"1998","unstructured":"V. Raman, B. Ravikumar and S. Srinivasa Rao, \u2018A Simplified NP-Complete MA-XSAT problem\u2019 Information Processing Letters, 65, (1998) 1\u20136.","journal-title":"Information Processing Letters"},{"key":"26_CR15","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J. M. Robson","year":"1986","unstructured":"J. M. Robson, \u2018Algorithms for the Maximum Independent Sets\u2019. Journal of Algorithms 7, (1986) 425\u2013440.","journal-title":"Journal of Algorithms"},{"key":"26_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/3-540-56992-8_22","volume-title":"Solving 3-Satisfiability in less than 1:579n steps","author":"I. Schiermeyer","year":"1993","unstructured":"I. Schiermeyer, \u2018Solving 3-Satisfiability in less than 1:579n steps\u2019, Lecture Notes in Computer Science, Springer Verlag 702, (1993) 379\u2013394."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46632-0_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T02:04:30Z","timestamp":1557021870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46632-0_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540669166","9783540466321"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-46632-0_26","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}