Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
From MaRDI portal
Publication:3758242
DOI10.1137/0215080zbMATH Open0621.68031OpenAlexW2164346692MaRDI QIDQ3758242FDOQ3758242
Authors: Mingte Chao, John V. Franco 
Publication date: 1986
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/305e2f8b6d156d3f8b6c1faab10f8f3e489ac6d6
Recommendations
- Probabilistic performance of a heurisic for the satisfiability problem
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- scientific article; zbMATH DE number 4102824
- The probabilistic analysis of a greedy satisfiability algorithm
- An exact and a randomized approach for the satisfiability problem
Cited In (39)
- Super solutions of random \((3 + p)\)-SAT
- A sharp threshold for a random constraint satisfaction problem
- A comparative runtime analysis of heuristic algorithms for satisfiability problems
- Typical case complexity of satisfiability algorithms and the threshold phenomenon
- On good algorithms for determining unsatisfiability of propositional formulas
- Solving non-uniform planted and filtered random SAT formulas greedily
- Solution clustering in random satisfiability
- Sharp thresholds of graph properties, and the $k$-sat problem
- Probabilistic bounds and algorithms for the maximum satisfiability problem
- Random \(k\)-SAT and the power of two choices
- Upper bounds on the satisfiability threshold
- Application of soil-structure interaction to off-shore foundations with specific reference to consolidation analysis
- Probabilistic performance of a heurisic for the satisfiability problem
- A threshold for unsatisfiability
- Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances
- An algorithm for random signed 3-SAT with intervals
- An efficient algorithm for the 3-satisfiability problem
- Rigorous results for random (\(2+p)\)-SAT
- Results related to threshold phenomena research in satisfiability: Lower bounds
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- Performances of pure random walk algorithms on constraint satisfaction problems with growing domains
- Biased random k‐SAT
- The cook-book approach to the differential equation method
- Title not available (Why is that?)
- On the thresholds in linear and nonlinear Boolean equations
- Phase transition in a random NK landscape model
- 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
- Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
- Lower bounds for random 3-SAT via differential equations
- Random 2-SAT: Results and problems
- Phase transitions of PP-complete satisfiability problems
- Exact satisfiability, a natural extension of set partition, and its average case behavior
- On Random 3-sat
- An average case analysis of a resolution principle algorithm in mechanical theorem proving.
- An exact and a randomized approach for the satisfiability problem
- Statistical physics analysis of the backtrack resolution of random 3-SAT instances
- Selecting Complementary Pairs of Literals
- Belief propagation on the random \(k\)-SAT model
- The scaling window of the 2-SAT transition
This page was built for publication: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3758242)
