| http://dbpedia.org/ontology/abstract
|
Em teoria da complexidade computacional, o … Em teoria da complexidade computacional, o problema da Divisão de Conjuntos é o seguinte problema de decisão:dada uma família F de subconjuntos de um conjunto finito S, decidir se existe uma partição de S em dois subconjuntos Sl, S2 de tal modo que todos os elementos de F são divididos por esta partição, i.e., nenhum dos elementos de F está completamente em S1 ou S2. A divisão de conjuntos é um dos problemas de .visão de conjuntos é um dos problemas de .
, En complejidad computacional, el problema … En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo. Visto como un problema de optimización, se llama el problema de división del máximo conjunto (en inglés Max Set Splitting) y consiste en encontrar la partición que maximiza el número de elementos divididos de F. Este es un problema (y NP-hard). El problema sigue siendo NP-hard incluso si todos los subconjuntos de F contienen el mismo número de elementos, todos ellos mayores que 1. Como problema de decisión, el Max Set Splitting, también llamado "Set Splitting" queda como sigue: dado un número entero k, ¿existe una partición de S que divida al menos k subconjuntos de F? Si k toma el valor de un parámetro dado, luego el "Set Splitting" posee complejidad parametrizada, es decir existe un algoritmo polinómico para cualquier valor de k.tmo polinómico para cualquier valor de k.
, In computational complexity theory, the se … In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.ometimes called hypergraph 2-colorability.
|
| http://dbpedia.org/ontology/wikiPageID
|
20751508
|
| http://dbpedia.org/ontology/wikiPageLength
|
5028
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1103882158
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Computational_complexity_theory +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Fixed-parameter_tractable +
, http://dbpedia.org/resource/Approximation_algorithm +
, http://dbpedia.org/resource/Not-all-equal_3-satisfiability +
, http://dbpedia.org/resource/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness +
, http://dbpedia.org/resource/Optimization_problem +
, http://dbpedia.org/resource/Graph_coloring +
, http://dbpedia.org/resource/Hypergraphs +
, http://dbpedia.org/resource/Property_B +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/APX-complete +
, http://dbpedia.org/resource/Maximum_cut +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Technical +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:NP-complete_problems +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Problem +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Set_splitting_problem?oldid=1103882158&ns=0 +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Set_splitting_problem +
|
| owl:sameAs |
http://yago-knowledge.org/resource/Set_splitting_problem +
, http://rdf.freebase.com/ns/m.05841ql +
, http://es.dbpedia.org/resource/Problema_de_la_divisi%C3%B3n_de_un_conjunto +
, http://dbpedia.org/resource/Set_splitting_problem +
, http://www.wikidata.org/entity/Q7456300 +
, http://pt.dbpedia.org/resource/Problema_da_divis%C3%A3o_de_conjuntos +
, https://global.dbpedia.org/id/4v1iN +
|
| rdf:type |
http://dbpedia.org/class/yago/Attribute100024264 +
, http://dbpedia.org/class/yago/State100024720 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Condition113920835 +
, http://dbpedia.org/class/yago/WikicatComputationalProblems +
, http://dbpedia.org/ontology/Disease +
, http://dbpedia.org/class/yago/Problem114410605 +
, http://dbpedia.org/class/yago/WikicatNP-completeProblems +
, http://dbpedia.org/class/yago/Difficulty114408086 +
|
| rdfs:comment |
Em teoria da complexidade computacional, o … Em teoria da complexidade computacional, o problema da Divisão de Conjuntos é o seguinte problema de decisão:dada uma família F de subconjuntos de um conjunto finito S, decidir se existe uma partição de S em dois subconjuntos Sl, S2 de tal modo que todos os elementos de F são divididos por esta partição, i.e., nenhum dos elementos de F está completamente em S1 ou S2. A divisão de conjuntos é um dos problemas de .visão de conjuntos é um dos problemas de .
, In computational complexity theory, the se … In computational complexity theory, the set splitting problem is the following decision problem: given a family F of subsets of a finite set S, decide whether there exists a partition of S into two subsets S1, S2 such that all elements of F are split by this partition, i.e., none of the elements of F is completely in S1 or S2. Set Splitting is one of Garey & Johnson's classical NP-complete problems. The problem is sometimes called hypergraph 2-colorability.ometimes called hypergraph 2-colorability.
, En complejidad computacional, el problema … En complejidad computacional, el problema de división de un conjunto (más comúnmente conocido en inglés como Set splitting problem) es el siguiente problema de decisión: dada una familia F de subconjuntos de un conjunto finito S, ¿existe una partición de S en dos subconjuntos S1 y S2 tales que ninguno de los elementos de F esté completamente en S1 o S2? Este problema es NP-completo.en S1 o S2? Este problema es NP-completo.
|
| rdfs:label |
Problema da divisão de conjuntos
, Problema de la división de un conjunto
, Set splitting problem
|
