{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T05:36:07Z","timestamp":1734586567675,"version":"3.30.2"},"reference-count":35,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2003,10,1]],"date-time":"2003-10-01T00:00:00Z","timestamp":1064966400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electronic Notes in Discrete Mathematics"],"published-print":{"date-parts":[[2003,10]]},"DOI":"10.1016\/s1571-0653(04)00462-7","type":"journal-article","created":{"date-parts":[[2004,10,24]],"date-time":"2004-10-24T03:07:12Z","timestamp":1098587232000},"page":"47-70","source":"Crossref","is-referenced-by-count":42,"special_numbering":"C","title":["Selecting Complementary Pairs of Literals"],"prefix":"10.1016","volume":"16","author":[{"given":"Alexis C.","family":"Kaporis","sequence":"first","affiliation":[]},{"given":"Lefteris M.","family":"Kirousis","sequence":"additional","affiliation":[]},{"given":"Efthimios","family":"Lalas","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB1","doi-asserted-by":"crossref","unstructured":"Achlioptas D.: Setting two variables at a time yields a new lower bound for random 3-SAT. In: Proc. 32nd Annual ACM Symposium on Theory of Computing (STOC '00) 28\u201337","DOI":"10.1145\/335305.335309"},{"issue":"1\u20132","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB2","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","article-title":"Lower bounds for random 3-SAT via differential equations","volume":"265","author":"Achlioptas","year":"2001","journal-title":"Theoretical Computer Science"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB3","doi-asserted-by":"crossref","unstructured":"Achlioptas D., Moore C.: The asymptotic order of the random k-SAT threshold. In: Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS '02)","DOI":"10.1109\/SFCS.2002.1182003"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB4","doi-asserted-by":"crossref","unstructured":"Achlioptas D., Sorkin G. B.: Optimal myopic algorithms for random 3-SAT. In: Proc. 41st Annual Symposium on Foundations of Computer Science (FOCS '00) 590\u2013600","DOI":"10.1109\/SFCS.2000.892327"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB5","unstructured":"Broder A., Frieze A., Upfal E.: On the satisfiability and maximum satisfiability of random 3-CNF formulas. In: Proc. 4th ACM-SIAM Symposium on Discrete Algorithms (SODA '93) 322\u2013330"},{"issue":"4","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB6","doi-asserted-by":"crossref","first-page":"1106","DOI":"10.1137\/0215080","article-title":"Probabilistic analysis of two heuristics for the 3-satisfiability problem","volume":"15","author":"Chao","year":"1986","journal-title":"SIAM J. of Comp"},{"issue":"3","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB7","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0255(90)90030-E","article-title":"Probabilistic analysis of a generalization of the unitclause literal selection heuristics for the k-satisfiability problem","volume":"51","author":"Chao","year":"1990","journal-title":"Inform. Sci"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB8","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal V., Reed B.: Mick gets some (the odds are on his side). In: Proc. 33rd Annual Symposium on the Foundation of Computer Science (FOCS '92) 620\u2013627","DOI":"10.1109\/SFCS.1992.267789"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB9","unstructured":"Cooper C., Frieze A., Sorkin, G. B.: A note on random 2-SAT with prescribed literal degrees. In: Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA '02) 316\u2013320"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB10","series-title":"Probabilistic Methods for Algorithmic Discrete Mathematics, Lecture Notes in Computer Science","first-page":"249","article-title":"Branching processes and their applications in the analysis of tree structures and tree algorithms","author":"Devroye","year":"1998"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB11","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1006\/jagm.1997.0867","article-title":"A general upper bound for the satisfiability threshold of random r-SAT","volume":"24","author":"Dubois","year":"1997","journal-title":"J. of Algorithms"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB12","unstructured":"Dubois O., Boufkhad Y., Mandler J.: Typical random 3-SAT formulae and the satisfiability threshold. In: Proc. 11th Symposium on Discrete Algorithms (SODA '00) 126\u2013127"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB13","unstructured":"Dubois O., Dequen G.: A backbone Search Heuristic for Efficient Solving of Hard 3-SAT Formulae. In Proc.: 17th International Joint Conference on Artificial Intelligence (IJCAI '01) 248\u2013253"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB14","unstructured":"Dubois O., Dequen G.: Renormalization as a function of clause lengths for solving k-SAT. In: Proc. 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT 02) 130\u2013132"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB15","unstructured":"Fernadez, W. de la Vega.: On random 2-SAT. Manuscript, 1992."},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB16","unstructured":"E. Friedgut, (Appendix by Bourgain, J.): Sharp thresholds of graph properties, and the k-SAT problem. J. AMS 12 (1997) 1017\u20131054"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB17","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1006\/jagm.1996.0016","article-title":"Analysis of two simple heuristics for random instances of k-SAT","volume":"20","author":"Frieze","year":"1996","journal-title":"J. Algorithms"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB18","unstructured":"Frieze A., Wormald N.: k-SAT: a tight threshold for moderately growing k. In: Proc. 5th International Symposium on the Theory and Applications of Satisfiability Testing (SAT 02) 1\u20136"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB19","unstructured":"Giannella C.: On Extending Two Threshold Algorithms to Non-Threshold Algorithms by Attaching the Unit Clause Rule, Master Thesis, University of Indiana, (1999). Available at: http:\/\/www.cs.indiana.edu\/~cgiannel\/work.html"},{"issue":"3","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB20","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1006\/jcss.1996.0081","article-title":"A threshold for unsatisfiability","volume":"53","author":"Goerdt","year":"1996","journal-title":"J. Comput. System Sci"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB21","unstructured":"M. T. Hajiaghayi and G. Sorkin, personal communication, 2002."},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB22","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","article-title":"Bounding the Unsatisfiability Threshold of Random 3-SAT","volume":"17","author":"Janson","year":"2000","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB23","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","article-title":"Approximation algorithms for combinatorial problems","volume":"9","author":"Johnson","year":"1974","journal-title":"Journal of Computer and System Sciences"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1002\/rsa.3240070105","article-title":"Tail bounds for occupancy and the satisfiability threshold conjecture","volume":"7","author":"Kamath","year":"1995","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB25","doi-asserted-by":"crossref","unstructured":"Kaporis, A. C., Kirousis, L. M., Lalas, E. G.: The probabilistic analysis of a greedy satisfiability algorithm. In: Proc. 10th Annual European Symposium on Algorithms (ESA 2002) Track A. 574\u2013585 Available at: http:\/\/students.ceid.upatras.gr\/~kaporis\/","DOI":"10.1007\/3-540-45749-6_51"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB26","unstructured":"Kaporis, A. C., Kirousis, L. M., Stamatiou, Y. C.: How to prove conditional randomness using the Principle of Deferred Decisions. TR, CTI, Greece, (2002) Available at: www.ceid.upatras.gr\/faculty\/kirousis\/kks-pdd02.ps. Also, available at: http:\/\/students.ceid.upatras.gr\/~kaporis\/"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB27","unstructured":"Kaporis, A. C., Kirousis, L. M., Stamatiou, Y. C., Vamvakari M., Zito M.: The Unsatisfiability Threshold Revisited. To appear in Discrete Mathematics. Available at: http:\/\/students.ceid.upatras.gr\/~kaporis\/"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB28","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","article-title":"Approximating the Unsatisfiability Threshold of Random Formulas","volume":"12","author":"Kirousis","year":"1998","journal-title":"Random Structures and Algorithms"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB29","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1017\/S0963548300001590","article-title":"On random 3-SAT","volume":"4","author":"Maftouhi","year":"1995","journal-title":"Combinatorics, Probability and Computing"},{"issue":"812","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB30","article-title":"Analytic and Algorithmic Solution of Random Satisfiability Problems","volume":"297","author":"M\u00e9zard","year":"2002","journal-title":"Science"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB31","doi-asserted-by":"crossref","unstructured":"M\u00e9zard M., Zecchina R.: The random k-Satisfiability problem: from an analytic solution to an efficient algorithm. Phys. Rev. E in press (2002)","DOI":"10.1103\/PhysRevE.66.056126"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB32","unstructured":"Mitchel D., Selman B., Levesque H.: Hard and easy distribution of SAT problems. In: Proc. 10th National Conference of Artifical Intelligence (AAAI 1992) 459\u2013465"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB33","unstructured":"Mitzemacher M.: Tight thresholds for the pure literal rule. TR, Digital Equipment Corporation, (1997) Available at: www.research.compaq.com\/SRC\/"},{"key":"10.1016\/S1571-0653(04)00462-7_NEWBIB34","series-title":"Probabilistic Methods for Algorithmic Discrete Mathematics, Lecture Notes in Computer Science","first-page":"1","article-title":"The probabilistic method","author":"Molloy","year":"1998"},{"issue":"4","key":"10.1016\/S1571-0653(04)00462-7_NEWBIB35","doi-asserted-by":"crossref","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","article-title":"Differential equations for random processes and random graphs","volume":"5","author":"Wormald","year":"1995","journal-title":"The Annals of Applied Probability"}],"container-title":["Electronic Notes in Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004627?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1571065304004627?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T03:46:23Z","timestamp":1734579983000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1571065304004627"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":35,"alternative-id":["S1571065304004627"],"URL":"https:\/\/doi.org\/10.1016\/s1571-0653(04)00462-7","relation":{},"ISSN":["1571-0653"],"issn-type":[{"type":"print","value":"1571-0653"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}