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

DOI10.1016/J.PHYSA.2019.122708OpenAlexW2974084700MaRDI QIDQ2164572FDOQ2164572

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

• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Gibbs states and the set of solutions of random constraint satisfaction problems
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the solution-space geometry of random constraint satisfaction problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Locating the phase transition in binary constraint satisfaction problems
• A general model and thresholds for random constraint satisfaction problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the phase transitions of random \(k\)-constraint satisfaction problems
• Random constraint satisfaction: Flaws and structure
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• Survey propagation: An algorithm for satisfiability
• Solution clustering in random satisfiability
• On the survey-propagation equations in random constraint satisfiability 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)