The satisfiability threshold for randomly generated binary constraint satisfaction problems
From MaRDI portal
Publication:5471050
DOI10.1002/rsa.20118zbMath1094.68092OpenAlexW4301417336WikidataQ57401505 ScholiaQ57401505MaRDI QIDQ5471050
Alan M. Frieze, Michael S. O. Molloy
Publication date: 6 June 2006
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.20118
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (7)
Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
Cites Work
- When does the giant component bring unsatisfiability?
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- The Resolution Complexity of Random Constraint Satisfaction Problems
- Models and thresholds for random constraint satisfaction problems
- A sharp threshold in proof complexity
- Random constraint satisfaction: A more accurate picture
This page was built for publication: The satisfiability threshold for randomly generated binary constraint satisfaction problems