Clustering phase of a general constraint satisfaction problem model d-k-CSP

DOI10.1016/J.PHYSA.2019.122708MaRDI QIDQ2164572zbMATH OpenOpenAlexFDO

Authors Wei Xu, Fuzhou Gong, Guangyan Zhou

Publication date 15 August 2022

Published in Physica A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.physa.2019.122708

zbMATH Keywords

constraint satisfaction problembelief propagationproblem hardnesssolution space structureclustering phase transition

Mathematics Subject Classification ID

Statistical mechanics, structure of matter (82-XX)

Cites work

• scientific article; zbMATH DE number 5547880 (Why is no real title available?)
• scientific article; zbMATH DE number 1448978 (Why is no real title available?)
• A general model and thresholds for random constraint satisfaction problems
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Locating the phase transition in binary constraint satisfaction problems
• On the phase transitions of random \(k\)-constraint satisfaction problems
• On the solution-space geometry of random constraint satisfaction problems
• On the survey-propagation equations in random constraint satisfiability problems
• Random constraint satisfaction: Flaws and structure
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Sharp thresholds of graph properties, and the $k$-sat problem
• Solution clustering in random satisfiability
• Survey propagation: An algorithm for satisfiability
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Two solutions to diluted p-spin models and XORSAT problems

Cited in

(4)

• Generating hard satisfiable instances by planting into random constraint satisfaction problem model with growing constraint scope length
• Recent Advances in Constraints
• The solution space structure of planted constraint satisfaction problems with growing domains
• Learning cluster-based structure to solve constraint satisfaction problems

This page was built for publication: Clustering phase of a general constraint satisfaction problem model \(d\)-\(k\)-CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164572)