{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T06:50:40Z","timestamp":1719903040282},"reference-count":26,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2013,10,1]],"date-time":"2013-10-01T00:00:00Z","timestamp":1380585600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T00:00:00Z","timestamp":1507766400000},"content-version":"vor","delay-in-days":1472,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"name":"International Joint grant of Royal Society"},{"DOI":"10.13039\/501100001732","name":"Danish National Research Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001732","id-type":"DOI","asserted-by":"crossref"}]},{"name":"The National Science Foundation of China","award":["61061130540"]},{"name":"Sino-Danish Center for the Theory of Interactive Computation"}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1016\/j.ic.2013.08.008","type":"journal-article","created":{"date-parts":[[2013,8,8]],"date-time":"2013-08-08T18:46:46Z","timestamp":1375987606000},"page":"117-124","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A new bound for 3-satisfiable MaxSat and its algorithmic application"],"prefix":"10.1016","volume":"231","author":[{"given":"Gregory","family":"Gutin","sequence":"first","affiliation":[]},{"given":"Mark","family":"Jones","sequence":"additional","affiliation":[]},{"given":"Dominik","family":"Scheder","sequence":"additional","affiliation":[]},{"given":"Anders","family":"Yeo","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2013.08.008_br0010","series-title":"IWPEC 2006","first-page":"264","article-title":"Kernels: Annotated, proper and induced","volume":"vol. 4169","author":"Abu-Khzam","year":"2006"},{"issue":"2","key":"10.1016\/j.ic.2013.08.008_br0020","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/0097-3165(86)90060-9","article-title":"Minimal non-two-colorable hypergraphs and minimal unsatisfiable formulas","volume":"43","author":"Aharoni","year":"1986","journal-title":"J. Combin. Theory Ser. A"},{"key":"10.1016\/j.ic.2013.08.008_br0030","doi-asserted-by":"crossref","first-page":"638","DOI":"10.1007\/s00453-010-9428-7","article-title":"Solving MAX-k-SAT above a tight lower bound","volume":"61","author":"Alon","year":"2011","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2013.08.008_br0040","series-title":"The Probabilistic Method","author":"Alon","year":"2000"},{"key":"10.1016\/j.ic.2013.08.008_br0050","unstructured":"H.K. B\u00fcning, O. Kullmann, Minimal Unsatisfiability and Autarkies, Handbook of Satisfiability, pp. 339\u2013401, http:\/\/dx.doi.org\/10.3233\/978-1-58603-929-5-339, chapter 11."},{"key":"10.1016\/j.ic.2013.08.008_br0060","series-title":"CiE 2009","first-page":"118","article-title":"Lower bounds for kernelizations and other preprocessing procedures","volume":"vol. 5635","author":"Chen","year":"2009"},{"key":"10.1016\/j.ic.2013.08.008_br0070","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/j.ipl.2010.04.010","article-title":"Note on Max Lin-2 above average","volume":"110","author":"Crowston","year":"2010","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/j.ic.2013.08.008_br0080","series-title":"SWAT 2010","first-page":"164","article-title":"Systems of linear equations over F2 and problems parameterized above average","volume":"vol. 6139","author":"Crowston","year":"2010"},{"key":"10.1016\/j.ic.2013.08.008_br0090","doi-asserted-by":"crossref","DOI":"10.1016\/j.tcs.2013.01.005","article-title":"Parameterized complexity of MaxSat above average","author":"Crowston","year":"2013","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2013.08.008_br0100","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1007\/s00453-011-9550-1","article-title":"A new lower bound on the maximum number of satisfied clauses in Max-SAT and its algorithmic applications","volume":"64","author":"Crowston","year":"2012","journal-title":"Algorithmica"},{"key":"10.1016\/j.ic.2013.08.008_br0110","series-title":"Parameterized Complexity","author":"Downey","year":"1999"},{"key":"10.1016\/j.ic.2013.08.008_br0120","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1016\/S0304-3975(01)00337-1","article-title":"Polynomial-time recognition of minimal unsatisfiable formulas with fixed clause-variable difference","volume":"289","author":"Fleischner","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2013.08.008_br0130","series-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"10.1016\/j.ic.2013.08.008_br0140","series-title":"FCT 2011","first-page":"138","article-title":"A new bound for 3-satisfiable MaxSat and its algorithmic application","volume":"vol. 6914","author":"Gutin","year":"2011"},{"key":"10.1016\/j.ic.2013.08.008_br0150","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0304-3975(85)90166-5","article-title":"Implications of forbidden structures for extremal algorithmic problems","volume":"40","author":"Huang","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.ic.2013.08.008_br0160","series-title":"IPEC 2011","first-page":"118","article-title":"Improved parameterized algorithms for constraint satisfaction","volume":"vol. 7112","author":"Kim","year":"2012"},{"key":"10.1016\/j.ic.2013.08.008_br0170","series-title":"SODA 2004","first-page":"330","article-title":"Locally satisfiable formulas","author":"Kr\u00e1l","year":"2004"},{"key":"10.1016\/j.ic.2013.08.008_br0180","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0166-218X(02)00406-7","article-title":"Lean clause-sets: Generalizations of minimally unsatisfiable clause-sets","volume":"130","author":"Kullmann","year":"2003","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2013.08.008_br0190","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1145\/322248.322260","article-title":"Complexity of partial satisfaction","volume":"28","author":"Lieberherr","year":"1981","journal-title":"J. ACM"},{"key":"10.1016\/j.ic.2013.08.008_br0200","series-title":"Complexity of partial satisfaction, II","author":"Lieberherr","year":"1982"},{"key":"10.1016\/j.ic.2013.08.008_br0210","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jagm.1998.0996","article-title":"Parameterizing above guaranteed values: MaxSat and MaxCut","volume":"31","author":"Mahajan","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/j.ic.2013.08.008_br0230","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/0166-218X(85)90050-2","article-title":"Solving satisfiability in less than 2n steps","volume":"10","author":"Monien","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.ic.2013.08.008_br0240","series-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier","year":"2006"},{"key":"10.1016\/j.ic.2013.08.008_br0250","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1016\/j.jcss.2004.04.009","article-title":"Minimal unsatisfiable formulas with bounded clause-variable difference are fixed-parameter tractable","volume":"69","author":"Szeider","year":"2004","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/j.ic.2013.08.008_br0260","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1137\/S0895480197326528","article-title":"On local versus global satisfiability","volume":"17","author":"Trevisan","year":"2004","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/j.ic.2013.08.008_br0270","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1006\/jagm.1994.1045","article-title":"On the approximation of maximum satisfiability","volume":"17","author":"Yannakakis","year":"1994","journal-title":"J. Algorithms"}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540113000850?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540113000850?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,10,14]],"date-time":"2018-10-14T02:56:01Z","timestamp":1539485761000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540113000850"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,10]]},"references-count":26,"alternative-id":["S0890540113000850"],"URL":"https:\/\/doi.org\/10.1016\/j.ic.2013.08.008","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2013,10]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A new bound for 3-satisfiable MaxSat and its algorithmic application","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ic.2013.08.008","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"Copyright \u00a9 2013 Elsevier Inc. All rights reserved.","name":"copyright","label":"Copyright"}]}}
