[phpBB Debug] PHP Warning: in file [ROOT]/ext/kinerity/bestanswer/event/main_listener.php on line 514: Undefined array key "poster_answers" Dominación eficiente - Foro de Wikipedia
En teoría de grafos, un '''conjunto dominante eficiente''' (también llamado '''conjunto e.d.''' o '''conjunto dominante perfecto independiente''') es un conjunto dominante con la propiedad adicional de que cada vértice (teoría de grafos)|vértice del gráfico (matemáticas discretas)|está dominado por exactamente un vértice del conjunto.
El '''problema de dominación eficiente''' (problema ED) pregunta si un gráfico dado contiene un conjunto dominante eficiente. El problema es NP-completo para gráficos generales.
== Definición ==
Un vértice v en un gráfico '''domina''' a sí mismo y a todos sus vecinos, es decir, cada vértice u tal que u = v o uv \in E. Un conjunto dominante D es un conjunto de vértices tal que cada vértice del gráfico está dominado por al menos un vértice en D. Un conjunto dominante ''eficiente'' fortalece esta condición al requerir que cada vértice esté dominado por '''exactamente un''' vértice en D.
Más formalmente, un conjunto de vértices D \subseteq V en un gráfico G = (V,E) es un conjunto dominante eficiente si para cada vértice v \in V, hay exactamente un d \in D tal que v está en la vecindad cerrada|Vecindad (teoría de grafos) N_G[d] de d.
== Complejidad ==
El problema de dominación eficiente es NP-completo para varias clases de gráficos, incluidos gráficos bipartitos, gráficos cordales y gráficos bipartitos cordales. Sin embargo, el problema se puede resolver en tiempo polinomial para ciertas clases de gráficos restringidas:
*Las gráficas dualmente cordales se pueden resolver en tiempo lineal
*Las gráficas sin AT se pueden resolver en tiempo polinómico
*Gráfico de intervalos|Los bigrafos de intervalo se pueden resolver en tiempo polinomial
== Problemas relacionados ==
El '''problema de dominación eficiente de los bordes''' (problema EED) es el análogo del borde del problema de dominación eficiente. Un '''conjunto eficiente de aristas dominantes''' M \subseteq E es un conjunto de aristas tal que cada arista e \in E es intersectada por exactamente una arista e' \in M. El problema EED se puede resolver en tiempo lineal para gráficos cordales y gráficos duales cordales.
El concepto también se extiende a los hipergráficos, donde se han establecido resultados de complejidad similares.
Objetos de teoría de grafos
Problemas NP-completos
Problemas computacionales en teoría de grafos
[h4] En teoría de grafos, un '''conjunto dominante eficiente''' (también llamado '''conjunto e.d.''' o '''conjunto dominante perfecto independiente''') es un conjunto dominante con la propiedad adicional de que cada vértice (teoría de grafos)|vértice del gráfico (matemáticas discretas)|está dominado por exactamente un vértice del conjunto. El '''problema de dominación eficiente''' (problema ED) pregunta si un gráfico dado contiene un conjunto dominante eficiente. El problema es NP-completo [url=viewtopic.php?t=1527]para[/url] gráficos generales.
== Definición == Un vértice v en un gráfico '''domina''' a sí mismo y a todos sus vecinos, es decir, cada vértice u tal que u = v o uv \in E. Un conjunto dominante D es un conjunto de vértices tal que cada vértice del gráfico está dominado por al menos un vértice en D. Un conjunto dominante ''eficiente'' fortalece esta condición al requerir que cada vértice esté dominado por '''exactamente un''' vértice en D.
Más formalmente, un conjunto de vértices D \subseteq V en un gráfico G = (V,E) es un conjunto dominante eficiente si [url=viewtopic.php?t=1527]para[/url] cada vértice v \in V, hay exactamente un d \in D tal que v está en la vecindad cerrada|Vecindad (teoría de grafos) N_G[d] de d.
== Complejidad == El problema de dominación eficiente es NP-completo [url=viewtopic.php?t=1527]para[/url] varias clases de gráficos, incluidos gráficos bipartitos, gráficos cordales y gráficos bipartitos cordales. Sin embargo, el problema se puede resolver en tiempo polinomial [url=viewtopic.php?t=1527]para[/url] ciertas clases de gráficos restringidas:
*Las gráficas dualmente cordales se pueden resolver en tiempo lineal *Las gráficas sin AT se pueden resolver en tiempo polinómico *Gráfico de intervalos|Los bigrafos de intervalo se pueden resolver en tiempo polinomial
== Problemas relacionados == El '''problema de dominación eficiente de los bordes''' (problema EED) es el análogo del borde del problema de dominación eficiente. Un '''conjunto eficiente de aristas dominantes''' M \subseteq E es un conjunto de aristas tal que cada arista e \in E es intersectada por exactamente una arista e' \in M. El problema EED se puede resolver en tiempo lineal [url=viewtopic.php?t=1527]para[/url] gráficos cordales y gráficos duales cordales.
El concepto también se extiende a los hipergráficos, donde se han establecido resultados de complejidad similares.
Objetos de teoría de grafos Problemas NP-completos Problemas computacionales en teoría de grafos [/h4]
More details: [url]https://en.wikipedia.org/wiki/Efficient_domination[/url]
Mobile version