Exact cover

English

Noun

1. Template:Lb 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^*.
   • Template:Quote-book
   • 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, Template:W 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

• French: Template:T-needed
• German: Template:T
• Italian: Template:T-needed

See also

• Template:L Template:Qualifier

Further reading

• Template:Pedia
• Template:Pedia