{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T13:15:48Z","timestamp":1773666948125,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540441809","type":"print"},{"value":"9783540457497","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45749-6_51","type":"book-chapter","created":{"date-parts":[[2007,7,4]],"date-time":"2007-07-04T15:42:44Z","timestamp":1183563764000},"page":"574-586","source":"Crossref","is-referenced-by-count":36,"title":["The Probabilistic Analysis of a Greedy Satisfiability Algorithm"],"prefix":"10.1007","author":[{"given":"Alexis C.","family":"Kaporis","sequence":"first","affiliation":[]},{"given":"Lefteris M.","family":"Kirousis","sequence":"additional","affiliation":[]},{"given":"Efthimios G.","family":"Lalas","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,8,29]]},"reference":[{"key":"51_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D.: Setting two variables at a time yields a new lower bound for random 3-SAT. Proc. 32nd AnnualA CM Symposium on Theory of Computing (STOC\u2019 00) 28\u201337","DOI":"10.1145\/335305.335309"},{"issue":"1\u20132","key":"51_CR2","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0304-3975(01)00159-1","volume":"265","author":"D. Achlioptas","year":"2001","unstructured":"Achlioptas, D.: Lower bounds for random 3-SAT via differential equations. Theoretical Computer Science 265 (1\u20132) (2001) 159\u2013185","journal-title":"Theoretical Computer Science"},{"key":"51_CR3","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Molloy, M.: The analysis of a list-coloring algorithm on a random graph. Proc. 38th Annual Symposium on Foundations of Computer Science (FOCS\u2019 97) 204\u2013212","DOI":"10.1109\/SFCS.1997.646109"},{"key":"51_CR4","doi-asserted-by":"crossref","unstructured":"Achlioptas, D., Moore, C.: Almost all graphs with average degree 4 are 3-colorable. Proc. 34th AnnualA CM Symposium on Theory of Computing (STOC\u2019 02) 199\u2013208","DOI":"10.1145\/509907.509940"},{"key":"51_CR5","doi-asserted-by":"crossref","unstructured":"Achlioptas D., Sorkin G.B.: Optimal myopic algorithms for random 3-SAT. Proc. 41st Annual Symposium on Foundations of Computer Science (FOCS\u2019 00) 590\u2013600","DOI":"10.1109\/SFCS.2000.892327"},{"key":"51_CR6","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Communications of the ACM 22 (1979) 251\u2013256","journal-title":"Communications of the ACM"},{"key":"51_CR7","unstructured":"Broder, A., Frieze, A., Upfal, E.: On the satisfiability and maximum satisfiability of random 3-CNF formulas. Proc. 4th ACM-SIAM Symposium on Discrete Algorithms (SODA\u2019 93) 322\u2013330"},{"issue":"4","key":"51_CR8","doi-asserted-by":"publisher","first-page":"1106","DOI":"10.1137\/0215080","volume":"15","author":"M. T. Chao","year":"1986","unstructured":"Chao, M. T., Franco, J.: Probabilistic analysis of two heuristics for the 3-satisfiability problem. SIAM J. of Comp. 15 (4) (1986) 1106\u20131118","journal-title":"SIAM J. of Comp."},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"Chv\u00e1tal, V., Reed, B.: Mick gets some (the odds are on his side). Proc. 33rd Annual Symposium on the Foundation of Computer Science (FOCS\u2019 92) 620\u2013627","DOI":"10.1109\/SFCS.1992.267789"},{"key":"51_CR10","unstructured":"Cooper, C., Frieze, A., Sorkin, G. B.: A note on random 2-SAT with prescribed literal degrees. Proc. 13th ACM-SIAMSymposium on Discrete Algorithms (SODA\u2019 02) 316\u2013320"},{"key":"51_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-662-12788-9_7","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"L. Devroye","year":"1998","unstructured":"Devroye, L.: Branching processes and their applications in the analysis of tree structures and tree algorithms. In: Habib, M., McDiarmid, C., Alfonsin, R., Reed, B. (eds.): Probabilistic Methods for Algorithmic Discrete Mathematics. Lecture Notes in Computer Science, Vol.. Springer-Verlag, Berlin (1998) 249\u2013314"},{"key":"51_CR12","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1006\/jagm.1997.0867","volume":"24","author":"O. Dubois","year":"1997","unstructured":"Dubois, O., Boufkhad, Y.: A general upper bound for the satisfiability threshold of random r-SAT. J. of Algorithms 24 (1997) 395\u2013420","journal-title":"J. of Algorithms"},{"key":"51_CR13","unstructured":"Dubois, O., Boufkhad, Y., Mandler, J.: Typical random 3-SAT formulae and the satisfiability threshold. In: Proc. 11th Symposium on Discrete Algorithms (SODA\u2019 00) 126\u2013127"},{"key":"51_CR14","first-page":"1017","volume":"12","author":"E. A. b. B. J. Friedgut","year":"1997","unstructured":"Friedgut, E., (Appendix by Bourgain, J.): Sharp thresholds of graph properties, and the k-SAT problem. J. AMS 12 (1997) 1017\u20131054","journal-title":"J. AMS"},{"key":"51_CR15","doi-asserted-by":"publisher","first-page":"312","DOI":"10.1006\/jagm.1996.0016","volume":"20","author":"A. Frieze","year":"1996","unstructured":"Frieze A., Suen S.: Analysis of two simple heuristics for random instances of k-SAT. J. Algorithms. 20 (1996) 312\u2013355","journal-title":"J. Algorithms"},{"key":"51_CR16","doi-asserted-by":"crossref","unstructured":"Janson, S., \u0141uczak, T., Ruci\u0144ski, A.: Random Graphs. Wiley (2000)","DOI":"10.1002\/9781118032718"},{"key":"51_CR17","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1002\/1098-2418(200009)17:2<103::AID-RSA2>3.0.CO;2-P","volume":"17","author":"S. Janson","year":"2000","unstructured":"Janson, S., Stamatiou, Y.C., Vamvakari, M.: Bounding the Unsatisfiability Threshold of Random 3-SAT. Random Structures and Algorithms 17 (2000) 103\u2013116","journal-title":"Random Structures and Algorithms"},{"key":"51_CR18","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/rsa.3240070105","volume":"7","author":"A. Kamath","year":"1995","unstructured":"Kamath, A., Motwani, R., Palem, K., Spirakis, P.: Tail bounds for occupancy and the satisfiability threshold conjecture. Random Structures and Algorithms 7 1995 59\u201380","journal-title":"Random Structures and Algorithms"},{"key":"51_CR19","unstructured":"Kaporis, A. C., Kirousis, L. M., Stamatiou, Y.C.: How to prove conditionalran-domness using the Principle of Deferred Decisions. TR, CTI, Greece, (2002) Available at: http:\/\/www.ceid.upatras.gr\/faculty\/kirousis\/kks-pdd02.ps"},{"key":"51_CR20","unstructured":"Kaporis, A. C., Kirousis, L. M., Stamatiou, Y.C., Vamvakari, M., Zito, M.: The Unsatisfiability Threshold Revisited. To appear in Discrete Mathematics"},{"key":"51_CR21","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1002\/(SICI)1098-2418(199805)12:3<253::AID-RSA3>3.0.CO;2-U","volume":"12","author":"L.M. Kirousis","year":"1998","unstructured":"Kirousis, L.M., Kranakis, E., Krizanc, D., Stamatiou, Y.C.: Approximating the Unsatisfiability Threshold of Random Formulas. Random Structures and Algorithms 12 (1998) 253\u2013269","journal-title":"Random Structures and Algorithms"},{"key":"51_CR22","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1017\/S0963548300001590","volume":"4","author":"M. Maftouhi","year":"1995","unstructured":"Maftouhi, M., Fernandez, V.: On random 3-SAT. Combinatorics, Probability and Computing 4 (1995) 190\u2013195","journal-title":"Combinatorics, Probability and Computing"},{"key":"51_CR23","unstructured":"Mitzenmacher, M.: Tight thresholds for the pure literal rule. TR, Digital Equipment Corporation, (1997) Available at: http:\/\/www.research.compaq.com\/SRC\/"},{"key":"51_CR24","series-title":"Lect Notes Comput Sci","first-page":"1","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"M. Molloy","year":"1998","unstructured":"Molloy, M.: The probabilistic method. In: Habib, M., McDiarmid, C., Alfonsin, R., Reed, B. (eds.): Probabilistic Methods for Algorithmic Discrete Mathematics. Lecture Notes in Computer Science, Vol.. Springer-Verlag, Berlin (1998) 1\u201335"},{"key":"51_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1006\/jctb.1996.0036","volume":"67","author":"B. Pittel","year":"1996","unstructured":"Pittel, B., Spencer, J., Wormald, N.C.: Sudden emergence of a giant k-core in a random graph. J. Combinatorial Theory, Series B. 67 (1996) 111\u2013151","journal-title":"J. Combinatorial Theory"},{"issue":"4","key":"51_CR26","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C. Differential equations for random processes and random graphs. The Annals of Applied Probability. 5 (4) (1995) 1217\u20131235","journal-title":"The Annals of Applied Probability"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45749-6_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,18]],"date-time":"2025-01-18T04:48:31Z","timestamp":1737175711000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45749-6_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441809","9783540457497"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-45749-6_51","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2002]]}}}