Monochromatic triangle
http://dbpedia.org/resource/Monochromatic_triangle an entity of type: WikicatNP-completeProblems
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?
rdf:langString
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.
rdf:langString
rdf:langString
Triángulo monocromático
rdf:langString
Monochromatic triangle
xsd:integer
1864042
xsd:integer
931302806
rdf:langString
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?
rdf:langString
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.
xsd:nonNegativeInteger
3696
