| dbo:abstract
|
- En teoría de grafos, una ruptura de un grafo no dirigido es un corte cuyo conjunto de corte forma un grafo bipartito completo. Un grafo es primo si no tiene ninguna ruptura. Las rupturas de un grafo pueden ser acomodadas siguiendo una estructura de árbol llamada descomposición de ruptura o descomposición conjunta, la cual puede ser construida en tiempo lineal. Esta descomposición ha sido utilizada para el reconocimiento rápido de grafos circulares y grafos de distancia hereditaria, así como para otros problemas en algoritmos de grafos. Las rupturas y descomposiciones de ruptura fueron introducidas por Cunningham (1982), quien también estudió variantes de estas mismas nociones para grafos dirigidos. (es)
- In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs. (en)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10314 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In graph theory, a split of an undirected graph is a cut whose cut-set forms a complete bipartite graph. A graph is prime if it has no splits. The splits of a graph can be collected into a tree-like structure called the split decomposition or join decomposition, which can be constructed in linear time. This decomposition has been used for fast recognition of circle graphs and distance-hereditary graphs, as well as for other problems in graph algorithms. Splits and split decompositions were first introduced by , who also studied variants of the same notions for directed graphs. (en)
- En teoría de grafos, una ruptura de un grafo no dirigido es un corte cuyo conjunto de corte forma un grafo bipartito completo. Un grafo es primo si no tiene ninguna ruptura. Las rupturas de un grafo pueden ser acomodadas siguiendo una estructura de árbol llamada descomposición de ruptura o descomposición conjunta, la cual puede ser construida en tiempo lineal. Esta descomposición ha sido utilizada para el reconocimiento rápido de grafos circulares y grafos de distancia hereditaria, así como para otros problemas en algoritmos de grafos. (es)
|
| rdfs:label
|
- Ruptura (teoría de grafos) (es)
- Split (graph theory) (en)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
