{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:17:52Z","timestamp":1725484672092},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_32","type":"book-chapter","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T22:33:34Z","timestamp":1180478014000},"page":"341-355","source":"Crossref","is-referenced-by-count":11,"title":["Improved Exact Algorithms for Max-Sat"],"prefix":"10.1007","author":[{"given":"Jianer","family":"Chen","sequence":"first","affiliation":[]},{"given":"Iyad A.","family":"Kanj","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"32_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/3-540-44985-X_10","volume-title":"Fixed parameter algorithms for dominating set and related problems on planar graphs","author":"J. Alber","year":"2000","unstructured":"J. Alber, H. L. Bodlaender, H. Fernau, and R. Niedermeier, Fixed parameter algorithms for dominating set and related problems on planar graphs, Lecture Notes in Computer Science 1851, (2000), pp. 97\u2013110. Accepted for publication in Algorithmica."},{"key":"32_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/3-540-44683-4_11","volume-title":"Refined search tree techniques for Dominating Set on planar graphs","author":"J. Alber","year":"2001","unstructured":"J. Alber, H. Fan, M. R. Fellows, H. Fernau, R. Niedermeier, F. Rosamond, and U. Stege, Refined search tree techniques for Dominating Set on planar graphs, Lecture Notes in Computer Science 2136, (2001), pp 111\u2013122."},{"key":"32_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-48224-5_22","volume-title":"Parameterized complexity: Exponential speed-up for planar graph problems","author":"J. Alber","year":"2001","unstructured":"J. Alber, H. Fernau, and R. Niedermeier, Parameterized complexity: Exponential speed-up for planar graph problems, in Proceedings of the 28th International Colloquium on Automata, Languages, and Programming (ICALP 2001), Lecture Notes in Computer Science 2076, (2001), pp 261\u2013272."},{"key":"32_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/3-540-63890-3_18","volume-title":"A theoretical framwork of hybrid approaches to Max-Sat","author":"T. Asano","year":"1997","unstructured":"T. Asano, K. Hori, T. Ono, and T. Hirata, A theoretical framwork of hybrid approaches to Max-Sat, Lecture Notes in Computer Science 1350, (1997), pp. 153\u2013162."},{"key":"32_CR5","unstructured":"T. Asano, and D. P. Williamson, Improved Aproximation Algorithms for Max-Sat, in Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms (SODA), (2000), pp. 96\u2013105."},{"key":"32_CR6","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0743-1066(85)90020-2","volume":"3","author":"P. Asirelli","year":"1985","unstructured":"P. Asirelli, M. de Santis, and A. Martelli, Integrity constraints in logic databases, Journal of Logic Programming 3, (1985), pp. 221\u2013232.","journal-title":"Journal of Logic Programming"},{"key":"32_CR7","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, An improved fixed parameter algorithm for vertex cover, Information Processing Letters 65, (1998), pp. 163\u2013168.","journal-title":"Information Processing Letters"},{"key":"32_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1007\/3-540-46632-0_26","volume-title":"Upper bounds for Max-Sat further improved","author":"N. Bansal","year":"1999","unstructured":"N. Bansal and V. Raman, Upper bounds for Max-Sat further improved, Lecture Notes in Computer Science 1741, (1999), pp. 247\u2013258."},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"R. Battiti and M. Protasi, Reactive research, a history base heuristic for Max-Sat, J. Exper. Algorithmics 2, No. 2, (1997).","DOI":"10.1145\/264216.264220"},{"key":"32_CR10","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/978-1-4613-0303-9_2","volume-title":"Handbook of Combinatorial Optimization","author":"Roberto Battiti","year":"1998","unstructured":"R. Battiti and M. Protasi, Approximate algorithms and heuristics for Max-Sat, in Handbook of Combinatorial Optimization 1, D. Z. Du and P. M. Pardalos Eds., (1998), pp. 77\u2013148."},{"key":"32_CR11","first-page":"465","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, J. Combinatorial Optimization 2, (1999), pp. 465\u2013474.","journal-title":"J. Combinatorial Optimization"},{"key":"32_CR12","unstructured":"R. Beigel, Finding mximum independent sets in sparse and general graphs, in Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201999), (1999), pp. 856\u2013857."},{"key":"32_CR13","unstructured":"R. Beigel and D. Eppstein, 3-coloring in time O(1.3446n): a no-MIS algorithm, in Proceedings of the 36th IEEE Symposium on Foundation of Computer Science (FOCS\u201995), (1995), pp. 442\u2013452."},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1006\/jcss.1997.1490","volume":"54","author":"L. Cai","year":"1997","unstructured":"L. Cai and J. Chen, On fixed-parameter tractability and approximation of NPhard optimization problems, Journal of Computer and System Sciences 54, (1997), pp. 465\u2013474.","journal-title":"Journal of Computer and System Sciences"},{"key":"32_CR15","unstructured":"L. Cai and D. Juedes, On the existence of subexponential-time parameterized algorithms, available at http:\/\/www.cs.uga.edu \/ ~ cai\/."},{"key":"32_CR16","unstructured":"J. Chen, D. K. Friesen, W. Jia, and I. A. Kanj, Using nondeterminism to design efficient deterministic algorithms, to appear in proceedings of the 21st annual conference on Foundations of Software Technology and Theoreical Computer Science (FSTTCS\u201901), December 13\u201315, (2001), Indian Institute of Science, Bangalore, India."},{"key":"32_CR17","series-title":"Lect Notes Comput Sci","volume-title":"On constrained minimum vertex covers of bibartite graphs: Improved Algorithms","author":"J. Chen","year":"2001","unstructured":"J. Chen and I. A. Kanj, On constrained minimum vertex covers of bibartite graphs: Improved Algorithms, Lecture Notes in Computer Science"},{"key":"32_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/3-540-46784-X_30","volume-title":"Vertex cover, further observations and further improvements","author":"J. Chen","year":"1999","unstructured":"J. Chen, I. A. Kanj, and W. Jia, Vertex cover, further observations and further improvements, Lecture Notes in Computer Science 1665, (1999), pp. 313\u2013324."},{"key":"32_CR19","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/1097-0037(200007)35:4<253::AID-NET3>3.0.CO;2-K","volume":"35","author":"J. Chen","year":"2000","unstructured":"J. Chen, L. Liu, and W. Jia, Improvement on Vertex Cover for low-degree graphs, Networks 35, (2000), pp. 253\u2013259.","journal-title":"Networks"},{"key":"32_CR20","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R. G. Downey","year":"1999","unstructured":"R. G. Downey and M. R. Fellows, Parameterized Complexity, New York, New York: Springer, (1999)."},{"key":"32_CR21","unstructured":"R. G. Downey, M. R. Fellows, and U. Stege, Parameterized complexity: A framework for systematically confronting computational intractability, in Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, F. Roberts, J. Kratochvil, and J. Nesetril, eds., AMS-DIMACS Proceedings Series 49, AMS, (1999), pp. 49\u201399."},{"key":"32_CR22","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-45022-X_21","volume":"1853","author":"E. Dantsin","year":"2000","unstructured":"E. Dantsin, M. Goerdt, E. A. Hirsch, and U. Sch\u00f6ning, Deterministic algorithms for k-SAT based on covering codes and local search, Lecture Notes in Compuer Science 1853, (2000), pp. 236\u2013247.","journal-title":"Lecture Notes in Compuer Science"},{"key":"32_CR23","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/321033.321034","volume":"7","author":"M. Davis","year":"1960","unstructured":"M. Davis and H. Putnam, A computing procedure for quantification theory, Journal of the ACM 7, (1960), pp. 201\u2013215.","journal-title":"Journal of the ACM"},{"key":"32_CR24","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1006\/jagm.2000.1141","volume":"38","author":"H. Fernau","year":"2001","unstructured":"H. Fernau and R. Niedermeier, An efficient exact algorithm for constraint bipartite vertex cover, Journal of Algorithms 38, (2001), pp. 374\u2013410.","journal-title":"Journal of Algorithms"},{"issue":"2","key":"32_CR25","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/356924.356929","volume":"16","author":"H. Gallaire","year":"1984","unstructured":"H. Gallaire, J. Minker, and J. M. Nicolas, Logic and databases: A deductive approach, Computing Surveys 16, No. 2, (1984), pp. 153\u2013185.","journal-title":"Computing Surveys"},{"key":"32_CR26","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, San Francisco, 1979."},{"key":"32_CR27","unstructured":"J. Gramm, E. A. Hirsch, R. Niedermeier, and P. Rossmanith, Newworstcase upper bounds for Max-2-Sat with application to Max-Cut, accepted for publication in Discrete Applied Mathematics (2001)."},{"key":"32_CR28","doi-asserted-by":"publisher","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) pp. 279\u2013303.","journal-title":"Computing"},{"key":"32_CR29","volume-title":"Building Expert Systems","author":"F. Hayes","year":"1983","unstructured":"F. Hayes, D. A. Waterman, and D. B. Lenat, Building Expert Systems, Reading Massachusetts: Addison Wesley, (1983)."},{"key":"32_CR30","unstructured":"O. Kullman and H. Luckhardt, Deciding propositional tautologies: Algorithms and their complexity, submitted for publication, available at http:\/\/www.cs-svr1.swan.ac.uk \/csoliver\/papers.html."},{"key":"32_CR31","doi-asserted-by":"publisher","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), pp. 335\u2013354.","journal-title":"Journal of Algorithms"},{"key":"32_CR32","unstructured":"T. A. Nguyen, W. A. Perkins, T. J. Laffey, and D. Pecora, Checking an expert systems knowledge base for consistency and completeness, IJCAI\u201985, Arvind Joshi Ed., Los Altos, CA, (1983), pp. 375\u2013378."},{"key":"32_CR33","doi-asserted-by":"publisher","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), pp. 63\u201388.","journal-title":"Journal of Algorithms"},{"key":"32_CR34","first-page":"425","volume":"6","author":"J. M. Robson","year":"1977","unstructured":"J. M. Robson, Algorithms for maximum independent set, Journal of Algorithms 6, (1977), pp. 425\u2013440.","journal-title":"Journal of Algorithms"},{"key":"32_CR35","doi-asserted-by":"crossref","unstructured":"R. J. Wallace, Enhancing maximum satisfiability algorithms with pure literal strategies, Lecture Notes on Artificial Intelligence 1081, (1996) pp. 388\u2013401.","DOI":"10.1007\/3-540-61291-2_67"}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T08:30:39Z","timestamp":1556440239000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}