Random constraint satisfaction: Flaws and structure
From MaRDI portal
Publication:5949019
DOI10.1023/A:1011454308633zbMath0992.68193OpenAlexW2071706116MaRDI QIDQ5949019
Ewan Macintyre, Ian Philip Gent, Patrick Prosser, Toby Walsh, Barbara M. Smith
Publication date: 12 November 2001
Published in: Constraints (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1023/a:1011454308633
Related Items (30)
Many hard examples in exact phase transitions ⋮ Partition search for non-binary constraint satisfaction ⋮ On the Integration of Singleton Consistencies and Look-Ahead Heuristics ⋮ The impact of search heuristics on heavy-tailed behaviour ⋮ Performances of pure random walk algorithms on constraint satisfaction problems with growing domains ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Combinatorial sharpness criterion and phase transition classification for random CSPs ⋮ Interleaving solving and elicitation of constraint satisfaction problems based on expected cost ⋮ Constraints for generating graphs with imposed and forbidden patterns: an application to molecular graphs ⋮ Dealing with satisfiability and \(n\)-ary CSPs in a logical framework ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Is computational complexity a barrier to manipulation? ⋮ New algorithms for bidirectional singleton arc consistency ⋮ Explorative anytime local search for distributed constraint optimization ⋮ Another look at the phenomenon of phase transition ⋮ Elicitation strategies for soft constraint problems with missing preferences: properties, algorithms and experimental studies ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Sharp thresholds for constraint satisfaction problems and homomorphisms ⋮ Constructing an asymptotic phase transition in random binary 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 ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ A new branch-and-filter exact algorithm for binary constraint satisfaction problems ⋮ Reasoning from last conflict(s) in constraint programming ⋮ When does the giant component bring unsatisfiability? ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
This page was built for publication: Random constraint satisfaction: Flaws and structure
