Random constraint satisfaction: A more accurate picture
From MaRDI portal
Publication:5949018
DOI10.1023/A:1011402324562zbMath0984.68085OpenAlexW2151266168MaRDI QIDQ5949018
Yannis C. Stamatiou, Evangelos Kranakis, Michael S. O. Molloy, Demetrios Achlioptas, Danny Krizanc, Lefteris M. Kirousis
Publication date: 10 February 2002
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1011402324562
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (26)
A Model for Phase Transition of Random Answer-Set Programs ⋮ Many hard examples in exact phase transitions ⋮ Partition search for non-binary constraint satisfaction ⋮ Statistical regimes across constrainedness regions ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ Identifying and exploiting problem structures using explanation-based constraint programming ⋮ The scaling window of the model \(d\)-\(k\)-CSP ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Des explications pour reconnaître et exploiter les structures cachées d'un problème combinatoire ⋮ Another look at the phenomenon of phase transition ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Rigorous results for random (\(2+p)\)-SAT ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Lower bounds for random 3-SAT via differential equations ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ The satisfiability threshold for randomly generated binary constraint satisfaction problems ⋮ The SAT-UNSAT transition for random constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Estimating satisfiability ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ When does the giant component bring unsatisfiability? ⋮ GA performance distributions and randomly generated binary constraint satisfaction problems. ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ On the constraint length of random \(k\)-CSP
This page was built for publication: Random constraint satisfaction: A more accurate picture
