Title: The Freuder Width in a General Model of Constraint Satisfaction Problem
Abstract: The Freuder width plays an important role for studying backtrack-free search. In this paper, we study a general random model of constraint satisfaction problem, named d-k-CSP, which exhibits exact satisfiability phase transition. We prove that the Freuder width of the model d-k-CSP is asymptotically equal to average degree.
Publication Year: 2016
Publication Date: 2016-12-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot