| dbo:abstract
|
- 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? (es)
- 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. (en)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3696 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- 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? (es)
- 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. (en)
|
| rdfs:label
|
- Triángulo monocromático (es)
- Monochromatic triangle (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
