exact cover

English

Noun

exact cover (plural exact covers)

1. (topology, combinatorics) Given 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^*.
   • 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:

     A finite set $\{S(\alpha _{i},\beta _{i})\vert 1\leq i\leq m\}$ is called an (eventual) exact cover if every (sufficiently large) positive integer occurs in exactly one $S(\alpha _{i},\beta _{i})$. If $\{S(\alpha _{i},\beta _{i})\}_{i=1}^{m}$ is an eventual exact cover, then $\textstyle \sum _{i=1}^{m}{\alpha _{i}^{-1}}=1$. […] In 1926, Beatty [Bea] studied the case $\beta =0$ and published the following result as a problem: $S(\alpha _{1},0)$ and $S(\alpha _{2},0)$ form an exact cover if and only if $\alpha _{1}$ is irrational and $\alpha _{1}^{2}+\alpha _{2}^{2}=1$.

   • 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.

Usage notes

• An exact cover may be defined as a partition that is comprised only of sets that are members of S.
• The general problem of finding an exact cover, S^*, for a given S and X is known as the exact cover problem. It is NP-complete.
• If an element of X belongs to a set T in S^*, that element is said to be covered by T.

Translations

Collection of subsets such that each element of the original set is contained in exactly one subset

• French: please add this translation if you can
• German: please add this translation if you can
• Italian: please add this translation if you can

See also

• tiling (geometry)

Further reading

• Partition of a set on Wikipedia.Wikipedia
• Knuth's Algorithm X on Wikipedia.Wikipedia