Estimating satisfiability
From MaRDI portal
Publication:765341
DOI10.1016/j.dam.2011.10.005zbMath1252.90069MaRDI QIDQ765341
Publication date: 19 March 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2011.10.005
90C27: Combinatorial optimization
Cites Work
- Unnamed Item
- Unnamed Item
- Regular random \(k\)-SAT: Properties of balanced formulas
- On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
- Pruning processes and a new characterization of convex geometries
- Almost all graphs with 2. 522\(n\) edges are not 3-colorable
- On the satisfiability threshold of formulas with three literals per clause
- The unsatisfiability threshold revisited
- A new look at survey propagation and its generalizations
- Approximating the unsatisfiability threshold of random formulas
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Tail bounds for occupancy and the satisfiability threshold conjecture
- Non Uniform Selection of Solutions for Upper Bounding the 3-SAT Threshold
- On the solution-space geometry of random constraint satisfaction problems
- Random constraint satisfaction: A more accurate picture