exact cover

plural exact covers

1. combinatoricsGiven a collection S of subsets of a set X, a subcollection S^* of S such that each element of X is contained in exactly one subset in S^*.

   2 more examples

   A finite set #92;#123;S(#92;alpha#95;i,#92;beta#95;i)#92;vert 1#92;lei#92;lem#92;#125; is called an (eventual) exact cover if every (sufficiently large) positive integer occurs in exactly one S(#92;alpha#95;i,#92;beta#95;i). If #92;#123;S(#92;alpha#95;i,#92;beta#95;i)#92;#125;#95;#123;i#61;1#125;ᵐ is an eventual exact cover, then #92;textstyle#92;sum#95;#123;i#61;1#125;ᵐ#123;#92;alpha#95;i#123;-1

   2000, R. Tijdeman, “Exact covers of balanced sequences and Fraenkel's conjecture”, in F. Halter-Koch, Robert F. Tichy, editors, Algebraic Number Theory and Diophantine Analysis: Proceedings of the International Conference, Walter de Gruyter, page 468

   2011, R. Lu, S. Liu, J. Zhang, Searching for Doubly Self-orthogonal Latin Squares, Jimmy Lee (editor), Principles and Practice of Constraint Programming: 17th International Conference CP 2011, Proceedings, Springer, LNCS 6876, page 542, It is straightforward to use clique algorithms to construct a (partial) solution of a given combinatorial problem which is represented as a set system. If the solution of the combinatorial problem corresponds to the exact cover of the set system, a substantially more efficient algorithm can be utilized because of this property.