Exact cover

EN Texto en inglés Aún no hay artículo en tu idioma: extracto en inglés.

In the mathematical field of combinatorics, given a collection S {\displaystyle {\mathcal {S}}} of subsets of a set X {\displaystyle X} , an exact cover is a subcollection S ∗ {\displaystyle {\mathcal {S}}^{*}} of S {\displaystyle {\mathcal {S}}} such that each element in X {\displaystyle X} is contained in exactly one subset in S ∗ {\displaystyle {\mathcal {S}}^{*}} . One says that each element in X {\displaystyle X} is covered by exactly one subset in S ∗ {\displaystyle {\mathcal {S}}^{*}} . An exact cover is a kind of cover. In other words, S ∗ {\displaystyle {\mathcal {S}}^{*}} is a partition of X {\displaystyle X} consisting of subsets contained in S {\displaystyle {\mathcal {S}}} . The exact cover problem to find an exact cover is a kind of constraint satisfaction problem. The elements of S {\displaystyle {\mathcal {S}}} represent choices and the elements of X {\displaystyle X} represent constraints. It is NP-hard and has a variety of applications, ranging from the optimization of airline flight schedules, cloud computing, and electronic circuit design. An exact cover problem involves the relation contains between subsets and elements. But an exact cover problem can be represented by any heterogeneous relation between a set of choices and a set of constraints. For example, an exact cover problem is equivalent to an exact hitting set problem, an incidence matrix, or a bipartite graph. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete and is one of Karp's 21 NP-complete problems. It is NP-complete even when each subset in S contains exactly three elements; this restricted problem is known as exact cover by 3-sets, often abbreviated X3C. Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX...