In the mathematical field of combinatorics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*. In other words, S* is a partition of X consisting of subsets contained in S.One says that each element in X is covered by exactly one subset in S*. An exact cover is a kind of cover. An exact cover problem can be represented by an incidence matrix or a bipartite graph.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Problem der exakten Überdeckung (de)
- Exact cover (en)
- Problème de la couverture exacte (fr)
- Exacte overdekking (nl)
- Cobertura exata (pt)
- 精确覆盖问题 (zh)
|
| rdfs:comment
| - Das Problem der exakten Überdeckung (englisch Exact cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP-vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP-vollständig sind. (de)
- Le problème de la couverture exacte est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp. (fr)
- In de wiskunde is exacte overdekking een bijzonder geval van het begrip overdekking van een verzameling. Een exacte overdekking van een verzameling van deelverzamelingen van een verzameling is een deelverzameling zodat elk element van juist één keer in een deelverzameling uit zit. Het beslissingsprobleem over het bestaan van een exacte overdekking en het vinden van de exacte overdekking zijn gerelateerde problemen uit de computationele meetkunde. Het vinden van een overdekking is NP-volledig en een van Karps 21 NP-volledige problemen. (nl)
- 在一个全集X中若干子集的集合为S，精确覆盖是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。 在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题，也是卡普的二十一个NP-完全问题之一。 (zh)
- In the mathematical field of combinatorics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*. In other words, S* is a partition of X consisting of subsets contained in S.One says that each element in X is covered by exactly one subset in S*. An exact cover is a kind of cover. An exact cover problem can be represented by an incidence matrix or a bipartite graph. (en)
- Na matemática, dada uma coleção de subconjuntos de um conjunto X, uma cobertura exata é uma subcoleção de de tal que cada elemento de X está contido em exatamente um subconjunto em . Pode-se dizer que cada elemento de X é coberto por exatamente um subconjunto em . Uma cobertura exata é um tipo de cobertura. Um problema de cobertura exata pode ser representado por uma matriz de incidência ou por um grafo bipartido. O problema da cobertura exata padrão pode ser generalizado ligeiramente para envolver não apenas "exatamente uma" restrição, mas também "no máximo uma" restrição. (pt)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Das Problem der exakten Überdeckung (englisch Exact cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP-vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP-vollständig sind. (de)
- In the mathematical field of combinatorics, given a collection S of subsets of a set X, an exact cover is a subcollection S* of S such that each element in X is contained in exactly one subset in S*. In other words, S* is a partition of X consisting of subsets contained in S.One says that each element in X is covered by exactly one subset in S*. An exact cover is a kind of cover. 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. The exact cover problem is a kind of constraint satisfaction problem. An exact cover problem can be represented by an incidence matrix or a bipartite graph. Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer. The standard exact cover problem can be generalized slightly to involve not only "exactly one" constraints but also "at-most-one" constraints. Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The n queens problem is a slightly generalized exact cover problem. (en)
- Le problème de la couverture exacte est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp. (fr)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
