An empirical study of phase transitions in binary constraint satisfaction problems
empirical study of phase transition behavior in CSPshard problemsmushy regionrandom binary constraint satisfaction problemssearch phase transitions
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
- Backtrack Programming
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Easy problems are sometimes hard
- Experimental evaluation of preprocessing algorithms for constraint satisfaction problems
- Exploiting the deep structure of constraint problems
- scientific article; zbMATH DE number 3902655 (Why is no real title available?)
- scientific article; zbMATH DE number 3904630 (Why is no real title available?)
- scientific article; zbMATH DE number 67483 (Why is no real title available?)
- scientific article; zbMATH DE number 1149402 (Why is no real title available?)
- Locating the phase transition in binary constraint satisfaction problems
- Needed: An Empirical Science of Algorithms
- The hardest constraint problems: A double phase transition
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Easy problems are sometimes hard
- On the average similarity degree between solutions of random \(k\)-SAT and random CSPs.
- Backtracking algorithms for disjunctions of temporal constraints
- Partition search for non-binary constraint satisfaction
- Modelling and solving temporal reasoning as propositional satisfiability
- A CSP search algorithm with responsibility sets and kernels
- Concurrent search for distributed CSPs
- An optimal coarse-grained arc consistency algorithm
- Phase transitions and the search problem
- Refining the phase transition in combinatorial search
- Locating the phase transition in binary constraint satisfaction problems
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
- Asymptotic and finite size parameters for phase transitions: Hamiltonian circuit as a case study
- Phase transitions in integer linear problems
- A general model and thresholds for random constraint satisfaction problems
- scientific article; zbMATH DE number 2084721 (Why is no real title available?)
- Phase Transition for Maximum Not-All-Equal Satisfiability
- scientific article; zbMATH DE number 1369843 (Why is no real title available?)
- Phase transitions of contingent planning problem
- Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
- On the phase transitions of random \(k\)-constraint satisfaction problems
- Constructing an asymptotic phase transition in random binary constraint satisfaction problems
- Graph representation of the fixed route dial-a-ride problem
- Hybrid search for minimal perturbation in dynamic CSPs
- Range and Roots: two common patterns for specifying and propagating counting and occurrence constraints
This page was built for publication: An empirical study of phase transitions in binary constraint satisfaction problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674179)
