An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems

Abstract

We provide an optimal randomized linear-time algorithm for locally consistent constraints satisfaction problems with binary constraints and show that the algorithm can be derandomized.

Keywords

• asymptotically
• optimal
• linear-time
• algorithm
• locally
• consistent
• constraint
• satisfaction
• problems