A Fast Recognition Algorithm of CRC Constraint Networks
相接行凸约束网络的快速识别算法

Constraint networks provide a useful framework for the formulation of many problems in computer science. In general, constraint satisfaction problems are NP-Complete. Many problems specially restrict the structure of constraints or the form of the constraints, then allow them to be solved efficiently. For the identification of such tractable constraints, much work has been devoted to the study of special classes of constraints or constraint networks. As pointed out by Deville et al., a class of connected row-convex(CRC)constraints is shown to be tractable.This paper intrnds to finds to fint an efficient recognition algorithm for the class of constraint networks.In this paper,a standardized form for the CRC constraint matrix is proposed based on the related finding on CRC constranint network.The basic characteristics of the standardized form are analyzed,and a fast algorithm is provided for the recognition of CRC constraint networks based on a recognition algorithm of the RC constraint network,properties of PQ tree(a tree composed by P nodes and Qnodes)and an indexed matrix representation of constraints.The time complexity of the algorithm is O(n3d2),where n is the number of variables in aconstraint network and d is the maximum size of the domain for wach variable.It reaches the optimum time complexity for a CRC constraint network recognition algorithm,and hence provides afeasible solution to practical CRC constraint satisfaction problems.