Satisfiability Transition and Experiments on a Random Constraint Satisfaction Problem Model
Wei Xu · International Journal of Hybrid Information Technology · 2014
Random constraint satisfaction problem models play a significant role in computer science.They provide instances for benchmarking algorithms, help inform the design of algorithms and heuristics, and provide insight into problem hardness.In this paper, model RA which was revised from classical model A, was studied.When parameter k satisfied 3 k , model RA has the same satisfiability transition with model RB, which was revised from classical model B and has already got considerable theoretical and practical studies.We also compared the performances of fundamental algorithms on model RA with on model RB.