Publication | Closed Access
Sharp thresholds for constraint satisfaction problems and homomorphisms
31
Citations
28
References
2008
Year
Mathematical ProgrammingConstraint SolvingEngineeringGraph TheoryConstraint SatisfactionAutomated ReasoningDomain Size ThreeSat SolvingHypergraph HomomorphismComputational ComplexityComputer ScienceSharp ThresholdsDiscrete MathematicsCombinatorial OptimizationSatisfiabilityInteger ProgrammingConstraint Programming
Abstract We determine under which conditions certain natural models of random constraint satisfaction problems have sharp thresholds of satisfiability. These models include graph and hypergraph homomorphism, the ( d , k , t )‐model, and binary constraint satisfaction problems with domain size three. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008
| Year | Citations | |
|---|---|---|
Page 1
Page 1