earticle

영어

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 k ≥ 3, 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.