Analysis of Two Simple Heuristics on a Random Instance ofk-sat

Recommendations

Probabilistic performance of a heurisic for the satisfiability problem
The probabilistic analysis of a greedy satisfiability algorithm
Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
scientific article; zbMATH DE number 2083805

Cited in

(48)

A fast parallel SAT-solver -- efficient workload balancing
On good algorithms for determining unsatisfiability of propositional formulas
Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT
A perspective on certain polynomial-time solvable classes of satisfiability
A sharp threshold for a random constraint satisfaction problem
A sharp threshold in proof complexity yields lower bounds for satisfiability search
Satisfiability threshold for random XOR-CNF formulas
Belief propagation on the random \(k\)-SAT model
Super solutions of random \((3 + p)\)-SAT
Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
Waiter-client and client-waiter colourability and \(k\)-SAT games
Maximum independent sets on random regular graphs
Typical case complexity of satisfiability algorithms and the threshold phenomenon
An algorithm for random signed 3-SAT with intervals
The scaling window of the 2-SAT transition
The decimation process in random k-SAT
Strong Refutation Heuristics for Random k-SAT
Selecting Complementary Pairs of Literals
A general model and thresholds for random constraint satisfaction problems
Sharp thresholds of graph properties, and the k-sat problem
The phase transition in random horn satisfiability and its algorithmic implications
The cook-book approach to the differential equation method
scientific article; zbMATH DE number 1369843 (Why is no real title available?)
Phase transitions of contingent planning problem
The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
Smooth and sharp thresholds for random{k}-XOR-CNF satisfiability
The probabilistic analysis of a greedy satisfiability algorithm
Deep learning: a statistical viewpoint
On the solution-space geometry of random constraint satisfaction problems
A sharp threshold for the phase transition of a restricted satisfiability problem for Horn clauses
Rigorous results for random (2+p)-SAT
Random 2-SAT: Results and problems
Results related to threshold phenomena research in satisfiability: Lower bounds
Lower bounds for random 3-SAT via differential equations
Upper bounds on the satisfiability threshold
Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
Bounding the scaling window of random constraint satisfaction problems
On the thresholds in linear and nonlinear Boolean equations
Fast sampling of satisfying assignments from random k-SAT with applications to connectivity
\texttt{WalkSAT} is linear on random 2-SAT
On the satisfiability of random 3-SAT formulas with \(k\)-wise independent clauses
Belief propagation guided decimation on random k-XORSAT
Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
On threshold properties of k-SAT: An additive viewpoint
The asymptotic k-SAT threshold
Finite size scaling for the core of large random hypergraphs
Solution clustering in random satisfiability

This page was built for publication: Analysis of Two Simple Heuristics on a Random Instance ofk-sat

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4876696)