Locating the phase transition in binary constraint satisfaction problems
From MaRDI portal
Publication:2674182
DOI10.1016/0004-3702(95)00052-6OpenAlexW2071639741MaRDI QIDQ2674182
Publication date: 22 September 2022
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0004-3702(95)00052-6
constraint satisfactionmushy regionsearch phase transitionscrossover pointexpectation and variance of number of solutions
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (22)
Partition search for non-binary constraint satisfaction ⋮ 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 ⋮ Modelling and solving temporal reasoning as propositional satisfiability ⋮ Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ An empirical study of phase transitions in binary constraint satisfaction problems ⋮ An upper (lower) bound for Max (Min) CSP ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ Hybrid search for minimal perturbation in dynamic CSPs ⋮ A Model to Study Phase Transition and Plateaus in Relational Learning ⋮ Concurrent search for distributed CSPs ⋮ Constraint satisfaction -- algorithms and complexity analysis ⋮ On the phase transitions of random \(k\)-constraint satisfaction problems ⋮ Determining if (FC-) (conflict-directed) backjumping visits a given node is NP-hard ⋮ Frozen development in graph coloring ⋮ Bounding the scaling window of random constraint satisfaction problems ⋮ Random constraint satisfaction: easy generation of hard (satisfiable) instances ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ Reasoning from last conflict(s) in constraint programming ⋮ A Lagrangian reconstruction of GENET
Cites Work
- Network-based heuristics for constraint-satisfaction problems
- Exploiting the deep structure of constraint problems
- An empirical study of phase transitions in binary constraint satisfaction problems
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Locating the phase transition in binary constraint satisfaction problems
