| http://dbpedia.org/ontology/abstract
|
In graph theory and theoretical computer s … In graph theory and theoretical computer science, the monochromatic triangle problem is an algorithmic problem on graphs,in which the goal is to partition the edges of a given graph into two triangle-free subgraphs. It is NP-complete but fixed-parameter tractable on graphs of bounded treewidth. tractable on graphs of bounded treewidth.
, El problema del triángulo monocromático es … El problema del triángulo monocromático es un problema de decisión que pertenece a la clase de los problemas NP-completos.
* Entrada: Un grafo no dirigido G(V,E), donde V es un conjunto de n vértices y E es el conjunto de aristas.
* Pregunta: ¿Puede el conjunto E ser particionado en dos conjuntos disjuntos E1 y E2, tales que ninguno de los dos grafos G1(V,E1) y G2(V,E2) contengan un triángulo; es decir, tal que para todos los vértices de E1 y E2, no exista un conjunto {u,v,w} tal que las aristas {u,v}, {u,w}, {v,w} estén definidas?istas {u,v}, {u,w}, {v,w} estén definidas?
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/RamseyTheory_K5_no_mono_K3.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageID
|
1864042
|
| http://dbpedia.org/ontology/wikiPageLength
|
3696
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
931302806
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Logic_of_graphs +
, http://dbpedia.org/resource/Ramsey%27s_theorem +
, http://dbpedia.org/resource/Decision_problem +
, http://dbpedia.org/resource/Triangle-free_graph +
, http://dbpedia.org/resource/Theoretical_computer_science +
, http://dbpedia.org/resource/Graph_theory +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Treewidth +
, http://dbpedia.org/resource/Courcelle%27s_theorem +
, http://dbpedia.org/resource/Category:NP-complete_problems +
, http://dbpedia.org/resource/Category:Graph_coloring +
, http://dbpedia.org/resource/File:RamseyTheory_K5_no_mono_K3.svg +
, http://dbpedia.org/resource/Monadic_second-order_logic +
, http://dbpedia.org/resource/Fixed-parameter_tractable +
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:Reflist +
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Graph_coloring +
, http://dbpedia.org/resource/Category:NP-complete_problems +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Monochromatic_triangle?oldid=931302806&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/RamseyTheory_K5_no_mono_K3.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Monochromatic_triangle +
|
| owl:sameAs |
https://global.dbpedia.org/id/4sEVU +
, http://dbpedia.org/resource/Monochromatic_triangle +
, http://es.dbpedia.org/resource/Tri%C3%A1ngulo_monocrom%C3%A1tico +
, http://rdf.freebase.com/ns/m.0621_m +
, http://yago-knowledge.org/resource/Monochromatic_triangle +
, http://www.wikidata.org/entity/Q6901448 +
|
| rdf:type |
http://dbpedia.org/class/yago/Difficulty114408086 +
, http://dbpedia.org/class/yago/Condition113920835 +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/Problem114410605 +
, http://dbpedia.org/class/yago/Attribute100024264 +
, http://dbpedia.org/class/yago/State100024720 +
, http://dbpedia.org/class/yago/WikicatNP-completeProblems +
|
| rdfs:comment |
El problema del triángulo monocromático es … El problema del triángulo monocromático es un problema de decisión que pertenece a la clase de los problemas NP-completos.
* Entrada: Un grafo no dirigido G(V,E), donde V es un conjunto de n vértices y E es el conjunto de aristas.
* Pregunta: ¿Puede el conjunto E ser particionado en dos conjuntos disjuntos E1 y E2, tales que ninguno de los dos grafos G1(V,E1) y G2(V,E2) contengan un triángulo; es decir, tal que para todos los vértices de E1 y E2, no exista un conjunto {u,v,w} tal que las aristas {u,v}, {u,w}, {v,w} estén definidas?istas {u,v}, {u,w}, {v,w} estén definidas?
, In graph theory and theoretical computer s … In graph theory and theoretical computer science, the monochromatic triangle problem is an algorithmic problem on graphs,in which the goal is to partition the edges of a given graph into two triangle-free subgraphs. It is NP-complete but fixed-parameter tractable on graphs of bounded treewidth. tractable on graphs of bounded treewidth.
|
| rdfs:label |
Triángulo monocromático
, Monochromatic triangle
|
