The Probabilistic Analysis of a Greedy Satisfiability Algorithm
- 29 August 2002
- book chapter
- Published by Springer Nature
- p. 574-586
- https://doi.org/10.1007/3-540-45749-6_51
Abstract
No abstract availableKeywords
This publication has 18 references indexed in Scilit:
- The analysis of a list-coloring algorithm on a random graphPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Lower bounds for random 3-SAT via differential equationsTheoretical Computer Science, 2001
- Bounding the unsatisfiability threshold of random 3-SATRandom Structures & Algorithms, 2000
- Random GraphsPublished by Wiley ,2000
- Branching Processes and Their Applications in the Analysis of Tree Structures and Tree AlgorithmsPublished by Springer Nature ,1998
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT FormulaeJournal of Algorithms, 1997
- Analysis of Two Simple Heuristics on a Random Instance ofk-satJournal of Algorithms, 1996
- Tail bounds for occupancy and the satisfiability threshold conjectureRandom Structures & Algorithms, 1995
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability ProblemSIAM Journal on Computing, 1986
- New methods to color the vertices of a graphCommunications of the ACM, 1979