Conjunto dominante: diferenças entre revisões
Sem fontes, sem cat |
|||
Linha 1: | Linha 1: | ||
{{for|Dominator in control flow graphs|Dominator (graph theory)}} |
|||
{{Sem-fontes|data=julho de 2015}} |
|||
[[Ficheiro:Dominating-set.svg|right|frame|Conjunto dominante (Vértices vermelhos).]] |
|||
Na teoria dos grafos, um '''conjunto dominante''' para o grafo G = (V, E) é um subconjunto D de V de tal modo que cada vértice que não está em D é adjacente a pelo menos um membro de D. O número de dominação γ(G) é o número de vértices em um menor conjunto dominante de G. |
|||
[[File:Dominating-set.svg|frame|right|Dominating sets (red vertices).]] |
|||
'''O problema do conjunto dominante''' refere-se a testar se γ(G) ≤ K para um dado grafo G e entrada K; É um clássico problema de decisão da classe NP-Completude na Teoria da complexidade computacional (Garey & Johnson 1979). Portanto, acredita-se que não existe um algoritmo eficiente que encontra um menor conjunto dominante para um dado grafo. |
|||
Em [https://pt.wikipedia.org/wiki/Teoria_dos_grafos| Teoria dos grafos], um '''conjunto dominante''' para um [https://pt.wikipedia.org/w/index.php?title=Teoria_dos_grafos&redirect=no| grafo]''G'' = (''V'', ''E'') é um [https://pt.wikipedia.org/wiki/Subconjunto| subconjunto] ''D'' de ''V'' de tal modo que cada vértice que não está em ''D'' é adjacente a pelo menos um membro de ''D''. O ''número de dominação'' γ(''G'') é o número de vértices em um menor conjunto dominante de G'. |
|||
O '''problema de conjunto dominante''' refere-se a testar se γ(''G'') ≤ ''K'' para um dado grafo ''G'' e entrada ''K''; É um clássico [https://pt.wikipedia.org/wiki/Problema_de_decis%C3%A3o| problema de decisão] [https://pt.wikipedia.org/wiki/NP-completoin| NP-completo] em [https://pt.wikipedia.org/wiki/Complexidade_computacional| Teoria de complexidade computacional] {{harv|Garey|Johnson|1979}}. Portanto, acredita-se que não existe um [https://pt.wikipedia.org/wiki/Complexidade_de_tempo| algoritmo eficiente] que encontra um menor conjunto dominante para um dado grafo. |
|||
As figuras (a)-(c) à direita mostram exemplos de árvores para conjuntos dominantes de um grafo. Em cada exemplo, cada vértice branco é adjacente a pelo menos um vértice vermelho, e dizemos que o vértice branco é dominado pelo vértice vermelho. O número de dominação do grafo é 2: Os exemplos (b)-(c) mostram que cada conjunto dominante possui dois vértices, e que pode ser verificado que não há conjunto dominante com apenas um vértice. |
As figuras (a)-(c) à direita mostram exemplos de árvores para conjuntos dominantes de um grafo. Em cada exemplo, cada vértice branco é adjacente a pelo menos um vértice vermelho, e dizemos que o vértice branco é dominado pelo vértice vermelho. O número de dominação do grafo é 2: Os exemplos (b)-(c) mostram que cada conjunto dominante possui dois vértices, e que pode ser verificado que não há conjunto dominante com apenas um vértice. |
||
==História== |
|||
== Dominação independente == |
|||
Conjuntos dominantes estão intimamente relacionados a conjuntos independentes: um conjunto independente é também um conjunto dominante se, e somente se, é um conjunto independente máximo, de modo que qualquer conjunto independente máximo em um grafo é necessariamente também um conjunto dominante mínimo. Assim, o menor conjunto independente máximo também é o menor conjunto dominante independente. O '''número de dominação independente '''i(G) de um grafo G é o tamanho do menor conjunto independente (ou, de forma equivalente, o tamanho da menor conjunto independente máxima). |
|||
Como {{harvtxt|Hedetniemi|Laskar|1990}} mostra, o problema de dominação foi estudado a partir da década de 1950, mas a taxa de pesquisas aumentou significativamente em meados de 1970. Sua lista de bibliografias inclui mais de 300 artigos relacionados à dominação em grafos. |
|||
==Limites== |
|||
Seja ''G'' um grafo com ''n'' ≥ 1 vertices e seja Δ o grau máximo do grafo. Os seguintes limites sobre γ(''G'') são conhecidos {{harv|Haynes|Hedetniemi|Slater|1998a|loc=Chapter 2}}: |
|||
* Um vértice pode dominar a maioria dos outros Δ vértices; Portanto, γ(''G'') ≥ ''n''/(1 + Δ). |
|||
* O conjunto de todos os vértices é um conjunto dominante sobre qualquer grafo; Portanto, γ(''G'') ≤ ''n''. |
|||
* Se não há vértices isolados em ''G'', então há dois conjuntos dominantes disjuntos em ''G''; Veja [https://en.wikipedia.org/wiki/Domatic_number| domatic partition] para detalhes. Portanto, em qualquer grafo sem vértices isolados é válido que γ(''G'') ≤ ''n''/2. |
|||
==Dominação independente== |
|||
Conjuntos dominantes estão intimamente relacionados a [https://pt.wikipedia.org/wiki/Conjunto_independentes| conjuntos independentes]: um conjunto independente é também um conjunto dominante se, e somente se, é um ''conjunto independente máximo'', de modo que qualquer conjunto independente máximo em um grafo é necessariamente também um conjunto dominante mínimo. Assim, o menor conjunto independente máximo também é o menor conjunto dominante independente. O '''número de dominação independente''' ''i''(''G'') de um grafo ''G'' é o tamanho do menor conjunto independente (ou, de forma equivalente, o tamanho da menor conjunto independente máxima). |
|||
O conjunto dominante mínimo num grafo não será necessariamente independente, mas o tamanho do conjunto dominante mínimo é sempre inferior ou igual ao tamanho de um máximo conjunto independente mínimo, isto é, γ(''G'') ≤ ''i''(''G''). |
|||
Há famílias de grafos em que um maior conjunto independente mínimo é um conjunto mínimo de dominação. Por examplo, {{harvtxt|Allan|Laskar|1978}} mostre que γ(''G'') = ''i''(''G'') se ''G'' é um [https://en.wikipedia.org/wiki/Claw-free_graph| claw-free graph], grafo claw-free. |
|||
Um grafo ''G'' é dito um '''grafo de dominação-perfeita''' se γ(''H'') = ''i''(''H'') em cada [[induced subgraph] | subrafo induzido] de ''H'' em ''G''. Uma vez que um subgrafo induzido de um grafo claw-free é também claw-free, segue-se que a cada grafo claw-free é também de dominação-perfeito {{harv|Faudree|Flandrin|Ryjáček|1997}}. |
|||
===Exemplos=== |
|||
As figuras (a) e (b) são conjuntos dominantes independentes, enquanto que a figura (c) ilustra um conjunto dominante que não é um conjunto independente. |
|||
Para qualquer grafo ''G'', seu [https://en.wikipedia.org/wiki/Line_graph| line grafo], grafo de linha, ''L''(''G'') é claw-free, e portanto, um maior conjunto independente mínimo é também um conjunto dominante mínimo em ''L''(''G''). Um conjunto independente em ''L''(''G'') corresponde a um [https://pt.wikipedia.org/wiki/Acoplamento_tridimensional| acoplamento] em ''G'', e um conjunto dominante em ''L''(''G'') corresponde a um conjunto de arestas dominantes em ''G''. Portanto, um máximo acoplamento mínimo tem o mesmo tamanho que um conjunto de arestas dominantes. |
|||
== Algoritmo e complexidade computacional == |
|||
Existe um par de tempo polinomial [https://pt.wikipedia.org/wiki/Redu%C3%A7%C3%A3o_linear| L-Redução] entre o problema conjunto dominante mínimo e o [https://pt.wikipedia.org/wiki/Cobertura_de_v%C3%A9rtices_(teoria_dos_grafos)| problema de cobertura de um conjunto] {{harv|Kann|1992|pp=108–109}}. Estas reduções mostram que um algoritmo eficiente para o problema do conjunto dominante mínimo iria fornecer um algoritmo eficiente para o problema da conjunto de cobertura e vice-versa. Além disso, as reduções mantém a [https://pt.wikipedia.org/wiki/Algoritmo_de_aproxima%C3%A7%C3%A3o | algoritmo de aproximação]: Para qualquer α, um algoritmo α-aproximação em tempo polinomial para conjuntos dominantes mínimos proporcionaria um algoritmo α-aproximação em tempo polinomial para o problema do conjunto de cobertura e vice-versa. Ambos os problemas são, na verdade [https://en.wikipedia.org/wiki/APX#Related_complexity_classes| Log-APX-complete].<ref>{{cite journal|last1=Escoffier|first1=Bruno|last2=Paschos|first2=Vangelis Th.|title=Completeness in approximation classes beyond APX|journal=Theoretical Computer Science|date=2006|volume=359|issue=1-3|pages=369–377|doi=10.1016/j.tcs.2006.05.023}}</ref> |
|||
O problema de conjunto de cobertura é um problema [https://pt.wikipedia.org/wiki/NP-dif%C3%ADcil| NP-Difícil] – a versão de decisão do conjunto de cobertura foi um dos [https://es.wikipedia.org/wiki/Lista_de_21_problemas_NP-completos_de_Karp | 21 problemas da lista de Karp], que foram mostrados para ser [https://pt.wikipedia.org/wiki/NP-completo| NP-Completo] já em 1972. Daí as reduções para mostrar que o conjunto dominante problema é NP-Difícil também. |
|||
A aproximabilidade do conjunto de cobertura também é bem conhecida: um fator de aproximação logarítmica pode ser encontrado usando um [https://pt.wikipedia.org/wiki/Algoritmo_guloso| simples algoritmo guloso], e encontrar um fator de aproximação sublogaritmico é NP-Difícil.Mais especificamente, o algoritmo guloso fornece um fator 1 + log |''V''| de aproximação para um conjunto dominante mínimo, e {{harvtxt|Raz|Safra|1997}} mostram que nenhum algoritmo pode alcançar um fator de aproximação melhor do que ''c'' log |''V''| por algum ''c'' > 0 a menos que [https://en.wikipedia.org/wiki/P_versus_NP_problem| P = NP]. |
|||
===L-reduções=== |
|||
O seguinte par de reduções {{harv|Kann|1992|pp=108–109}} ) mostra que o problema do conjunto dominante mínimo e o problema de conjunto de cobertura são equivalentes sob L-reduções: dado um exemplo de um problema, podemos construir uma instância equivalente de outro problema. |
|||
'''Do conjunto dominante para o conjunto de cobertura''' |
|||
Dado um grafo ''G'' = (''V'', ''E'') com ''V'' = {1, 2, ..., ''n''}, construir uma instância para conjunto de cobertura (''S'', ''U'') da seguinte forma: o universo ''U'' é ''V'', e é da família ''S'' = {''S''<sub>1</sub>, ''S''<sub>2</sub>, ..., ''S''<sub>''n''</sub>} tal que ''S''<sub>v</sub> consiste no vértice ''v'' e todos os vértices adjacentes a ''v'' em ''G''. |
|||
Agora, se ''D'' é um conjunto dominante de ''G'', então ''C'' = {''S''<sub>''v''</sub> : ''v'' ∈ ''D''} é uma solução viável do problema de cobertura do conjunto, com |''C''| = |''D''|. Por outro lado, se ''C'' = {''S''<sub>''v''</sub> : ''v'' ∈ ''D''} é uma solução viável do problema de conjunto de cobertura, então ''D'' é um conjunto dominante para ''G'', com |''D''| = |''C''|. |
|||
Portanto, o tamanho mínimo de um conjunto dominante para ''G'' é igual ao tamanho mínimo da cobertura por conjunto para (''S'', ''U''). Além do mais, existe um algoritmo simples que mapeia o conjunto dominante em uma cobertura por conjunto do mesmo tamanho, e vice versa. Em particular, a existência de uma α-aproximação eficiente para cobertura de conjuntos possibilita a existência de uma α-aproximação para o problema de minimizar o conjunto dominante. |
|||
[[File:Dominating-set-2.svg|right]] |
|||
::Por exemplo, dado o grafo ''G'' exibido à direita, nós construiremos uma instância de um conjunto de cobertura com o universo ''U'' = {1, 2, ..., 6} e os subconjuntos ''S''<sub>1</sub> = {1, 2, 5}, ''S''<sub>2</sub> = {1, 2, 3, 5}, ''S''<sub>3</sub> = {2, 3, 4, 6}, ''S''<sub>4</sub> = {3, 4}, ''S''<sub>5</sub> = {1, 2, 5, 6}, and ''S''<sub>6</sub> = {3, 5, 6}. Neste exemplo, ''D'' = {3, 5} é um conjunto dominante para ''G'' – esta corresponde à um conjunto de cobertura ''C'' = {''S''<sub>3</sub>, ''S''<sub>5</sub>}. Por exemplo, o vértice 4 ∈ ''V'' é dominado pelo vértice 3 ∈ ''D'', e o elemento 4 ∈ ''U'' está contido no conjunto ''S''<sub>3</sub> ∈ ''C''. |
|||
'''Do conjunto de cobertura para o conjunto dominante''' |
|||
Seja (''S'', ''U'') uma instância do problema do conjunto de cobertura com o universo ''U'' e a família de subconjuntos ''S'' = {''S''<sub>''i''</sub> : ''i'' ∈ ''I''};Supomos que ''U'' e o índice definido ''I'' são disjuntos. Construir um grafo ''G'' = (''V'', ''E'') como segue: o conjunto de vértices é ''V'' = ''I'' ∪ ''U'', existe uma aresta {''i'', ''j''} ∈ ''E'' entre cada par ''i'', ''j'' ∈ ''I'', e também existe uma aresta {''i'', ''u''} para cada ''i'' ∈ ''I'' e ''u'' ∈ ''S''<sub>''i''</sub>. Isto é, ''G'' é um [https://en.wikipedia.org/wiki/Split_graph| split graph]: ''I'' é um [https://pt.wikipedia.org/wiki/Clique| clique] e ''U'' é um [https://en.wikipedia.org/wiki/Independent_set_(graph_theory)| conjunto independente]]. |
|||
Agora, se ''C'' = {''S''<sub>''i''</sub> : ''i'' ∈ ''D''} é uma solução viável do problema do conjunto de cobertura para um subconjunto ''D'' ⊆ ''I'', então ''D'' é um conjunto dominante para ''G'', com |''D''| = |''C''|: Em primeiro lugar, para cada ''u'' ∈ ''U'' existe um ''i'' ∈ ''D'' tal que ''u'' ∈ ''S''<sub>''i''</sub>, e por construção, ''u'' e ''i'' são adjacentes em ''G''; Portanto, ''u'' é dominado por ''i''.Em segundo lugar, uma vez que ''D'' deve ser não-vazia, cada ''i'' ∈ ''I'' é adjacente a um vértice no ponto ''D''. |
|||
Por outro lado, seja ''D'' um conjunto dominante de ''G''. Em seguida, é possível construir outro conjunto dominante ''X'' tal que |''X''| ≤ |''D''| e ''X'' ⊆ ''I'': basta substituir cada ''u'' ∈ ''D'' ∩ ''U'' por um vizinho ''i'' ∈ ''I'' de ''u''. Então, ''C'' = {''S''<sub>''i''</sub> : ''i'' ∈ ''X''} é uma solução viável do problema de conjunto de com |''C''| = |''X''| ≤ |''D''|. |
|||
[[File:Dominating-set-reduction.svg|right]] |
|||
::A ilustração do lado direito mostra a construção de ''U'' = {''a'', ''b'', ''c'', ''d'', ''e''}, ''I'' = {1, 2, 3, 4}, ''S''<sub>1</sub> = {''a'', ''b'', ''c''}, ''S''<sub>2</sub> = {''a'', ''b''}, ''S''<sub>3</sub> = {''b'', ''c'', ''d''}, e ''S''<sub>4</sub> = {''c'', ''d'', ''e''}. |
|||
::Neste exemplo, ''C'' = {''S''<sub>1</sub>, ''S''<sub>4</sub>} é um conjunto de cobertura; isto corresponde ao conjunto dominante ''D'' = {1, 4}. |
|||
::''D'' = {''a'', 3, 4} é um outro conjunto dominante para o grafo ''G''. Dado ''D'', podemos construir um conjunto dominante ''X'' = {1, 3, 4} que não é maior do que ''D'' e que é um subconjunto de ''I''. O conjunto dominante ''X''corresponde à cobertura conjunto ''C'' = {''S''<sub>1</sub>, ''S''<sub>3</sub>, ''S''<sub>4</sub>}. |
|||
===Casos especiais=== |
|||
Se o grafo apresentar um grau máximo Δ, então o algoritmo de aproximação ganancioso encontra uma ''O''(log Δ)-aproximação de um conjunto dominante mínimo. Para Δ fixo, está apto para o conjunto dominante para adesão [https://en.wikipedia.org/wiki/APX| APX]; Na verdade, é APX-completo.<ref>{{cite journal|last1=Papadimitriou|first1=Christos H.|last2=Yannakakis|first2=Mihailis|title=Optimization, Approximation, and Complexity Classes|journal=Journal of Computer and Systems Sciences|date=1991|volume=43|issue=3|pages=425–440|doi=10.1016/0022-0000(91)90023-X}}</ref> |
|||
O problema admite um [https://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme| PTAS]] para casos especiais tais como grafos de unidade de disco e grafos planares {{harv|Crescenzi|Kann|Halldórsson|Karpinski|2000}}. Um conjunto dominante mínimo pode ser encontrado em tempo linear com grafos séries-paralelo {{harv|Takamizawa|Nishizeki|Saito|1982}}. |
|||
===Algoritmos Exatos=== |
|||
Um conjunto dominante mínimo de um grafo de ''n''-vértices pode ser encontrado em tempo ''O''(2<sup>''n''</sup>''n'') inspecionando todos os subconjuntos de vértices. {{harvtxt|Fomin|Grandoni|Kratsch|2009}} mostram como encontrar um conjunto dominante mínimo no tempo ''O''(1.5137<sup>''n''</sup>) e espaço exponencial, e em tempo ''O''(1.5264<sup>''n''</sup>) e espaço polinomial. Um algoritmo rápido, utilizando tempo ''O''(1.5048<sup>''n''</sup>) foi encontrado por {{harvtxt|van Rooij|Nederlof|van Dijk|2009}}, que também mostram que o número de conjuntos de mínimos dominantes pode ser calculado neste momento. O número de conjuntos dominantes mínimo é no máximo 1.7159<sup>''n''</sup> e todos os tais conjuntos podem ser listadas em tempo ''O''(1.7159<sup>''n''</sup>) {{harv|Fomin|Grandoni|Pyatkin|Stepanov|2008}} . |
|||
===Complexidade Parametrizada=== |
|||
Encontrar um conjunto dominante de tamanho ''k'' desempenha um papel central na teoria da complexidade parametrizada. É o problema mais conhecido para a classe completa [https://en.wikipedia.org/wiki/Parameterized_complexity#W.5B2.5D| W[2]] e usada em muitas reduções para mostrar a indecidibilidade de outros problemas. Em particular, o problema não é um parâmetro fixo decidível no sentido de que nenhum algoritmo com o funcionamento de tempo ''f''(''k'')''n''<sup>O(1)</sup> para qualquer função ''f'' existe a menos que a hierarquia W reduz a FPT=W[2]. Por outro lado, se o grafo de entrada é plana, o problema permanece NP-Difícil, mas um algoritmo de parâmetro fixo é conhecido. Na verdade, o problema tem um kernel de tamanho linear em ''k'' {{harv|Alber|Fellows|Niedermeier|2004}}, e tempos de execução que são exponencial √''k'' e cúbico em ''n'' pode ser obtido através da aplicação de [https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_din%C3%A2mica| programação dinâmica] para uma [https://en.wikipedia.org/wiki/Branch-decomposition| branch decomposition] do kernel {{harv|Fomin|Thilikos|2006}}. |
|||
== Variantes == |
|||
A conjectura de Vizing, [https://en.wikipedia.org/wiki/Vizing%27s_conjecture| Conjectura de Vizing], relaciona o número dominação de um produto cartesiano de grafos para o número dominação de seus fatores. |
|||
Houve muito trabalho em conjuntos dominantes ligados. Se ''S'' é um conjunto dominante ligado, pode-se formar um [https://en.wikipedia.org/wiki/Spanning_tree| spanning tree] de ''G'' em ''S'' forma o conjunto de vértices não-folhas da árvore; Inversamente, se ''T'' é qualquer árvore geradora em um gráfico com mais de dois vértices, os vértices não-folha de ''T'' formam um conjunto dominante ligado. Portanto, encontrar conjuntos dominantes mínimos ligados é equivalente a encontrar spanning trees com o maior número possível de folhas. |
|||
Um ''conjunto total dominante'' é um conjunto de vértices de tal forma que todos os vértices no grafo (incluindo os vértices no dominante ajustados entre si) têm um vizinho no conjunto dominante. A figura (c) acima mostra que o conjunto dominante que é conectado e um conjunto dominante total; Os exemplos nas figuras (a) e (b) não são. |
|||
Uma ''k-tupla de um conjunto dominante'' é um conjunto de vértices tal que cada vértice no grafo tem pelo menos ''k'' vizinhos do conjunto Um (1+log n)-aproximação de um conjunto mínimo k-tupla dominante pode ser encontrada em tempo polinomial {{harv|Klasing|Laforest|2004}}. Da mesma forma, um ''k-conjunto dominante'' é um conjunto de vértices tal que cada vértice que não está no conjunto tem pelo menos ''k'' vizinhos do conjunto. Enquanto todo grafo admite um k-conjunto dominante, apenas grafos com grau mínimo k-1 admitem um conjunto dominante com k-tupla. No entanto, mesmo se o grafo admite um conjunto dominante com k-tupla, um conjunto dominante mínimo com k-tupla pode ser k vezes maior do que um conjunto mínimo dominante k para o mesmo grafo {{harv|Förster|2013}}; Uma (1.7+log Δ)-aproximação de um K-conjunto mínimo dominante pode ser encontrado em tempo polinomial. |
|||
Uma partição domatic, [https://en.wikipedia.org/wiki/Domatic_number| domatic partition], é uma partição dos vértices em conjuntos disjuntos dominantes. O número domatic é o tamanho máximo de uma partição domatic. |
|||
Um [https://en.wikipedia.org/wiki/Eternal_dominating_set| Eternal dominating set] é uma versão dinâmica de dominação em que um vértice ''v'' em um conjunto dominante ''D'' é escolhido e substituído por um vizinho ''u'' (''u'' is not in ''D'') tal que o ''D'' modificado é um conjunto dominante e este processo pode ser repetido sobre qualquer sequência infinita de opções de vértices v. |
|||
== Software for searching minimum dominating set == |
|||
{| class="wikitable" |
|||
|- |
|||
!Name<br>(alphabetically) |
|||
!License |
|||
!API language |
|||
!Brief info |
|||
|- |
|||
|OpenOpt || BSD|| Python || Uses NetworkX graphs, can use free and commercial solvers, included / excluded vertices, see its [http://openopt.org/DSP dominating set] page for details and examples |
|||
|} |
|||
== See also == |
|||
O conjunto dominante mínimo num grafo não será necessariamente independente, mas o tamanho do conjunto dominante mínimo é sempre inferior ou igual ao tamanho de um conjunto independente mínimo*, isto é, γ(G) ≤ i(G). |
|||
* [https://en.wikipedia.org/wiki/Set_cover_problem| Set cover problem] |
|||
* [https://en.wikipedia.org/wiki/Bondage_number| Bondage number] |
|||
== References == |
|||
Há famílias de grafos em que um maior conjunto independente mínimo é um conjunto mínimo de dominação. Por exemplo, Allan & Laskar (1978) mostram que γ(G) = i(G) se G é um grafo ''claw-free''. |
|||
{{Reflist}} |
|||
*{{citation |
|||
Um grafo é dito grafo de dominação-perfeito se γ(H) = i(H) em cada subgrafo H de G. Uma vez que um subgrafo induzido de um grafo claw-free é também claw-free, segue-se que a cada grafo claw-free é também de dominação-perfeito (Faudree, Flandrin & Ryjáček 1997). |
|||
|last1= Alber | first1= Jochen |
|||
|author2-link=Michael Fellows|last2=Fellows|first2=Michael R |
|||
|last3=Niedermeier|first3= Rolf |
|||
|title=Polynomial-time data reduction for dominating set |
|||
|journal=[[Journal of the ACM]] |
|||
|volume= 51|pages= 363–384|year=2004 |
|||
|doi= 10.1145/990308.990309|issue=3 |
|||
}}. |
|||
*{{citation |
|||
| last1=Allan | first1 = Robert B. |
|||
| last2=Laskar | first2 = Renu |
|||
| title = On domination and independent domination numbers of a graph |
|||
| journal = Discrete Mathematics |
|||
| year = 1978 |
|||
| volume = 23 |
|||
| pages = 73–76 |
|||
| doi = 10.1016/0012-365X(78)90105-X |
|||
| issue = 2 |
|||
}}. |
|||
*{{citation |
|||
| last1=Crescenzi | first1=Pierluigi |
|||
| last2=Kann | first2=Viggo |
|||
| last3=Halldórsson | first3=Magnús |
|||
| last4=Karpinski | first4=Marek | authorlink4=Marek Karpinski |
|||
| last5=Woeginger | first5=Gerhard |
|||
| title=A Compendium of NP Optimization Problems |
|||
| contribution=Minimum dominating set |
|||
| url=http://www.nada.kth.se/~viggo/wwwcompendium/node11.html |
|||
| year=2000 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Faudree | first1 = Ralph | author1-link = Ralph Faudree |
|||
| last2 = Flandrin | first2 = Evelyne |
|||
| last3 = Ryjáček | first3 = Zdeněk |
|||
| doi = 10.1016/S0012-365X(96)00045-3 |
|||
| issue = 1–3 |
|||
| journal = Discrete Mathematics |
|||
| pages = 87–147 |
|||
| title = Claw-free graphs — A survey |
|||
| volume = 164 |
|||
| year = 1997 |
|||
| mr = 1432221 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Fomin | first1 = Fedor V. |
|||
| last2 = Grandoni | first2 = Fabrizio |
|||
| last3 = Kratsch | first3 = Dieter |
|||
| title = A measure & conquer approach for the analysis of exact algorithms |
|||
| journal = [[Journal of the ACM]] |
|||
| volume = 56 |
|||
| year = 2009 |
|||
| pages = 25:1–32 |
|||
| doi = 10.1145/1552285.1552286 |
|||
| issue = 5 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Fomin | first1 = Fedor V. |
|||
| last2 = Grandoni | first2 = Fabrizio |
|||
| last3 = Pyatkin | first3 = Artem |
|||
| last4 = Stepanov | first4 = Alexey |
|||
| title = Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications |
|||
| journal = ACM Transactions on Algorithms |
|||
| volume = 5 |
|||
| year = 2008 |
|||
| pages = 9:1–17 |
|||
| doi = 10.1145/1435375.1435384 |
|||
| issue = 1 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Fomin | first1 = Fedor V. |
|||
| last2 = Thilikos | first2 = Dimitrios M. |
|||
| doi = 10.1137/S0097539702419649 |
|||
| journal = SIAM Journal on Computing |
|||
| page = 281 |
|||
| title = Dominating sets in planar graphs: branch-width and exponential speed-up |
|||
| volume = 36 |
|||
| year = 2006 |
|||
| issue = 2}}. |
|||
*{{citation |
|||
| last1 = Förster | first1 = Klaus-Tycho. |
|||
| year = 2013 |
|||
| contribution = Approximating Fault-Tolerant Domination in General Graphs |
|||
| title = Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics [[ACM SIGACT#Conferences|ANALCO]] |
|||
| publisher = SIAM |
|||
| pages = 25–32 |
|||
| doi = 10.1137/1.9781611973037.4 |
|||
| isbn = 978-1-61197-254-2 |
|||
}}. |
|||
*{{Garey-Johnson}}, p. 190, problem GT2. |
|||
*{{citation |
|||
| title = A note on the complexity of minimum dominating set |
|||
| last = Grandoni | first = F. |
|||
| journal = Journal of Discrete Algorithms |
|||
| volume = 4 |
|||
| pages = 209–214 |
|||
| year = 2006 |
|||
| doi = 10.1016/j.jda.2005.03.002 |
|||
| issue = 2 |
|||
}}. |
|||
*{{citation |
|||
| title = Approximation algorithms for connected dominating sets |
|||
| journal = [[Algorithmica]] |
|||
| volume = 20 |
|||
| issue = 4 |
|||
| year = 1998 |
|||
| pages = 374–387 |
|||
| first1 = S. | last1 = Guha |
|||
| first2 = S. | last2 = Khuller |
|||
| doi = 10.1007/PL00009201 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Haynes | first1 = Teresa W. |
|||
| last2 = Hedetniemi | first2 = Stephen |
|||
| last3 = Slater | first3 = Peter |
|||
| title = Fundamentals of Domination in Graphs |
|||
| publisher = Marcel Dekker |
|||
| year = 1998a |
|||
| isbn = 0-8247-0033-3 |
|||
| oclc = 37903553 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Haynes | first1= Teresa W. |
|||
| last2 = Hedetniemi | first2 = Stephen |
|||
| last3 = Slater | first3 = Peter |
|||
| title = Domination in Graphs: Advanced Topics |
|||
| publisher = Marcel Dekker |
|||
| year = 1998b |
|||
| isbn = 0-8247-0034-1 |
|||
| oclc = 38201061 |
|||
}}. |
|||
*{{citation |
|||
| last1 = Hedetniemi | first1= S. T. |
|||
| last2 = Laskar | first2= R. C. |
|||
| title = Bibliography on domination in graphs and some basic definitions of domination parameters |
|||
| journal = [[Discrete Mathematics (journal)|Discrete Mathematics]] |
|||
| volume = 86 |
|||
| issue = 1–3 |
|||
| year = 1990 |
|||
| pages = 257–277 |
|||
| doi = 10.1016/0012-365X(90)90365-O |
|||
}}. |
|||
*{{citation|last1=Klasing|first1=Ralf|last2=Laforest|first2=Christian|title=Hardness results and approximation algorithms of k-tuple domination in graphs|journal=Information Processing Letters|volume=89|issue=2|year=2004|pages=75–83|doi=10.1016/j.ipl.2003.10.004}}. |
|||
*{{citation |
|||
| last = Kann | first = Viggo |
|||
| year = 1992 |
|||
| title = On the Approximability of NP-complete Optimization Problems |
|||
| url = http://www.csc.kth.se/~viggo/papers/phdthesis.pdf |
|||
| postscript = . PhD thesis, Department of Numerical Analysis and Computing Science, [[Royal Institute of Technology]], Stockholm |
|||
}}. |
|||
*{{citation |
|||
| last1 = Raz | first1 = R. | author1-link=Ran Raz |
|||
| last2 = Safra | first2 = S. |
|||
| year = 1997 |
|||
| contribution = A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP |
|||
| title = Proc. 29th Annual ACM [[Symposium on Theory of Computing]] |
|||
| publisher = ACM |
|||
| pages = 475–484 |
|||
| doi = 10.1145/258533.258641 |
|||
| isbn = 0-89791-888-6 |
|||
}}. |
|||
*{{citation |
|||
| title = Linear-time computability of combinatorial problems on series-parallel graphs |
|||
| journal = [[Journal of the ACM]] |
|||
| volume = 29 |
|||
| issue = 3 |
|||
| year = 1982 |
|||
| pages = 623–641 |
|||
| first1 = K. | last1 = Takamizawa |
|||
| first2 = T. | last2 = Nishizeki | author2-link = Takao Nishizeki |
|||
| first3 = N. | last3 = Saito |
|||
| doi = 10.1145/322326.322328 |
|||
}}. |
|||
*{{citation |
|||
| contribution = Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets |
|||
| title = Proc. 17th Annual European Symposium on Algorithms, ESA 2009 |
|||
| publisher = Springer |
|||
| series = Lecture Notes in Computer Science |
|||
| volume = 5757 |
|||
| pages = 554–565 |
|||
| year = 2009 |
|||
| first1 = J. M. M. | last1 = van Rooij |
|||
| first2 = J. | last2 = Nederlof |
|||
| first3 = T. C. | last3 = van Dijk |
|||
| doi = 10.1007/978-3-642-04128-0_50 |
|||
| isbn = 978-3-642-04127-3 |
|||
}}. |
|||
[[Category:Graph theory objects]] |
|||
{{Sem cat|data=julho de 2015}} |
|||
[[Category:NP-complete problems]] |
|||
[[Category:Computational problems in graph theory]] |
Revisão das 17h44min de 8 de julho de 2015
Em Teoria dos grafos, um conjunto dominante para um grafoG = (V, E) é um subconjunto D de V de tal modo que cada vértice que não está em D é adjacente a pelo menos um membro de D. O número de dominação γ(G) é o número de vértices em um menor conjunto dominante de G'.
O problema de conjunto dominante refere-se a testar se γ(G) ≤ K para um dado grafo G e entrada K; É um clássico problema de decisão NP-completo em Teoria de complexidade computacional (Garey & Johnson 1979). Portanto, acredita-se que não existe um algoritmo eficiente que encontra um menor conjunto dominante para um dado grafo. As figuras (a)-(c) à direita mostram exemplos de árvores para conjuntos dominantes de um grafo. Em cada exemplo, cada vértice branco é adjacente a pelo menos um vértice vermelho, e dizemos que o vértice branco é dominado pelo vértice vermelho. O número de dominação do grafo é 2: Os exemplos (b)-(c) mostram que cada conjunto dominante possui dois vértices, e que pode ser verificado que não há conjunto dominante com apenas um vértice.
História
Como Hedetniemi & Laskar (1990) mostra, o problema de dominação foi estudado a partir da década de 1950, mas a taxa de pesquisas aumentou significativamente em meados de 1970. Sua lista de bibliografias inclui mais de 300 artigos relacionados à dominação em grafos.
Limites
Seja G um grafo com n ≥ 1 vertices e seja Δ o grau máximo do grafo. Os seguintes limites sobre γ(G) são conhecidos (Haynes, Hedetniemi & Slater 1998a, Chapter 2):
- Um vértice pode dominar a maioria dos outros Δ vértices; Portanto, γ(G) ≥ n/(1 + Δ).
- O conjunto de todos os vértices é um conjunto dominante sobre qualquer grafo; Portanto, γ(G) ≤ n.
- Se não há vértices isolados em G, então há dois conjuntos dominantes disjuntos em G; Veja domatic partition para detalhes. Portanto, em qualquer grafo sem vértices isolados é válido que γ(G) ≤ n/2.
Dominação independente
Conjuntos dominantes estão intimamente relacionados a conjuntos independentes: um conjunto independente é também um conjunto dominante se, e somente se, é um conjunto independente máximo, de modo que qualquer conjunto independente máximo em um grafo é necessariamente também um conjunto dominante mínimo. Assim, o menor conjunto independente máximo também é o menor conjunto dominante independente. O número de dominação independente i(G) de um grafo G é o tamanho do menor conjunto independente (ou, de forma equivalente, o tamanho da menor conjunto independente máxima).
O conjunto dominante mínimo num grafo não será necessariamente independente, mas o tamanho do conjunto dominante mínimo é sempre inferior ou igual ao tamanho de um máximo conjunto independente mínimo, isto é, γ(G) ≤ i(G).
Há famílias de grafos em que um maior conjunto independente mínimo é um conjunto mínimo de dominação. Por examplo, Allan & Laskar (1978) mostre que γ(G) = i(G) se G é um claw-free graph, grafo claw-free.
Um grafo G é dito um grafo de dominação-perfeita se γ(H) = i(H) em cada [[induced subgraph] | subrafo induzido] de H em G. Uma vez que um subgrafo induzido de um grafo claw-free é também claw-free, segue-se que a cada grafo claw-free é também de dominação-perfeito (Faudree, Flandrin & Ryjáček 1997).
Exemplos
As figuras (a) e (b) são conjuntos dominantes independentes, enquanto que a figura (c) ilustra um conjunto dominante que não é um conjunto independente.
Para qualquer grafo G, seu line grafo, grafo de linha, L(G) é claw-free, e portanto, um maior conjunto independente mínimo é também um conjunto dominante mínimo em L(G). Um conjunto independente em L(G) corresponde a um acoplamento em G, e um conjunto dominante em L(G) corresponde a um conjunto de arestas dominantes em G. Portanto, um máximo acoplamento mínimo tem o mesmo tamanho que um conjunto de arestas dominantes.
Algoritmo e complexidade computacional
Existe um par de tempo polinomial L-Redução entre o problema conjunto dominante mínimo e o problema de cobertura de um conjunto (Kann 1992, pp. 108–109). Estas reduções mostram que um algoritmo eficiente para o problema do conjunto dominante mínimo iria fornecer um algoritmo eficiente para o problema da conjunto de cobertura e vice-versa. Além disso, as reduções mantém a | algoritmo de aproximação: Para qualquer α, um algoritmo α-aproximação em tempo polinomial para conjuntos dominantes mínimos proporcionaria um algoritmo α-aproximação em tempo polinomial para o problema do conjunto de cobertura e vice-versa. Ambos os problemas são, na verdade Log-APX-complete.[1]
O problema de conjunto de cobertura é um problema NP-Difícil – a versão de decisão do conjunto de cobertura foi um dos | 21 problemas da lista de Karp, que foram mostrados para ser NP-Completo já em 1972. Daí as reduções para mostrar que o conjunto dominante problema é NP-Difícil também.
A aproximabilidade do conjunto de cobertura também é bem conhecida: um fator de aproximação logarítmica pode ser encontrado usando um simples algoritmo guloso, e encontrar um fator de aproximação sublogaritmico é NP-Difícil.Mais especificamente, o algoritmo guloso fornece um fator 1 + log |V| de aproximação para um conjunto dominante mínimo, e Raz & Safra (1997) mostram que nenhum algoritmo pode alcançar um fator de aproximação melhor do que c log |V| por algum c > 0 a menos que P = NP.
L-reduções
O seguinte par de reduções (Kann 1992, pp. 108–109) ) mostra que o problema do conjunto dominante mínimo e o problema de conjunto de cobertura são equivalentes sob L-reduções: dado um exemplo de um problema, podemos construir uma instância equivalente de outro problema.
Do conjunto dominante para o conjunto de cobertura Dado um grafo G = (V, E) com V = {1, 2, ..., n}, construir uma instância para conjunto de cobertura (S, U) da seguinte forma: o universo U é V, e é da família S = {S1, S2, ..., Sn} tal que Sv consiste no vértice v e todos os vértices adjacentes a v em G.
Agora, se D é um conjunto dominante de G, então C = {Sv : v ∈ D} é uma solução viável do problema de cobertura do conjunto, com |C| = |D|. Por outro lado, se C = {Sv : v ∈ D} é uma solução viável do problema de conjunto de cobertura, então D é um conjunto dominante para G, com |D| = |C|.
Portanto, o tamanho mínimo de um conjunto dominante para G é igual ao tamanho mínimo da cobertura por conjunto para (S, U). Além do mais, existe um algoritmo simples que mapeia o conjunto dominante em uma cobertura por conjunto do mesmo tamanho, e vice versa. Em particular, a existência de uma α-aproximação eficiente para cobertura de conjuntos possibilita a existência de uma α-aproximação para o problema de minimizar o conjunto dominante.
- Por exemplo, dado o grafo G exibido à direita, nós construiremos uma instância de um conjunto de cobertura com o universo U = {1, 2, ..., 6} e os subconjuntos S1 = {1, 2, 5}, S2 = {1, 2, 3, 5}, S3 = {2, 3, 4, 6}, S4 = {3, 4}, S5 = {1, 2, 5, 6}, and S6 = {3, 5, 6}. Neste exemplo, D = {3, 5} é um conjunto dominante para G – esta corresponde à um conjunto de cobertura C = {S3, S5}. Por exemplo, o vértice 4 ∈ V é dominado pelo vértice 3 ∈ D, e o elemento 4 ∈ U está contido no conjunto S3 ∈ C.
Do conjunto de cobertura para o conjunto dominante Seja (S, U) uma instância do problema do conjunto de cobertura com o universo U e a família de subconjuntos S = {Si : i ∈ I};Supomos que U e o índice definido I são disjuntos. Construir um grafo G = (V, E) como segue: o conjunto de vértices é V = I ∪ U, existe uma aresta {i, j} ∈ E entre cada par i, j ∈ I, e também existe uma aresta {i, u} para cada i ∈ I e u ∈ Si. Isto é, G é um split graph: I é um clique e U é um conjunto independente].
Agora, se C = {Si : i ∈ D} é uma solução viável do problema do conjunto de cobertura para um subconjunto D ⊆ I, então D é um conjunto dominante para G, com |D| = |C|: Em primeiro lugar, para cada u ∈ U existe um i ∈ D tal que u ∈ Si, e por construção, u e i são adjacentes em G; Portanto, u é dominado por i.Em segundo lugar, uma vez que D deve ser não-vazia, cada i ∈ I é adjacente a um vértice no ponto D.
Por outro lado, seja D um conjunto dominante de G. Em seguida, é possível construir outro conjunto dominante X tal que |X| ≤ |D| e X ⊆ I: basta substituir cada u ∈ D ∩ U por um vizinho i ∈ I de u. Então, C = {Si : i ∈ X} é uma solução viável do problema de conjunto de com |C| = |X| ≤ |D|.
- A ilustração do lado direito mostra a construção de U = {a, b, c, d, e}, I = {1, 2, 3, 4}, S1 = {a, b, c}, S2 = {a, b}, S3 = {b, c, d}, e S4 = {c, d, e}.
- Neste exemplo, C = {S1, S4} é um conjunto de cobertura; isto corresponde ao conjunto dominante D = {1, 4}.
- D = {a, 3, 4} é um outro conjunto dominante para o grafo G. Dado D, podemos construir um conjunto dominante X = {1, 3, 4} que não é maior do que D e que é um subconjunto de I. O conjunto dominante Xcorresponde à cobertura conjunto C = {S1, S3, S4}.
Casos especiais
Se o grafo apresentar um grau máximo Δ, então o algoritmo de aproximação ganancioso encontra uma O(log Δ)-aproximação de um conjunto dominante mínimo. Para Δ fixo, está apto para o conjunto dominante para adesão APX; Na verdade, é APX-completo.[2]
O problema admite um PTAS] para casos especiais tais como grafos de unidade de disco e grafos planares (Crescenzi et al. 2000). Um conjunto dominante mínimo pode ser encontrado em tempo linear com grafos séries-paralelo (Takamizawa, Nishizeki & Saito 1982).
Algoritmos Exatos
Um conjunto dominante mínimo de um grafo de n-vértices pode ser encontrado em tempo O(2nn) inspecionando todos os subconjuntos de vértices. Fomin, Grandoni & Kratsch (2009) mostram como encontrar um conjunto dominante mínimo no tempo O(1.5137n) e espaço exponencial, e em tempo O(1.5264n) e espaço polinomial. Um algoritmo rápido, utilizando tempo O(1.5048n) foi encontrado por van Rooij, Nederlof & van Dijk (2009), que também mostram que o número de conjuntos de mínimos dominantes pode ser calculado neste momento. O número de conjuntos dominantes mínimo é no máximo 1.7159n e todos os tais conjuntos podem ser listadas em tempo O(1.7159n) (Fomin et al. 2008) .
Complexidade Parametrizada
Encontrar um conjunto dominante de tamanho k desempenha um papel central na teoria da complexidade parametrizada. É o problema mais conhecido para a classe completa W[2] e usada em muitas reduções para mostrar a indecidibilidade de outros problemas. Em particular, o problema não é um parâmetro fixo decidível no sentido de que nenhum algoritmo com o funcionamento de tempo f(k)nO(1) para qualquer função f existe a menos que a hierarquia W reduz a FPT=W[2]. Por outro lado, se o grafo de entrada é plana, o problema permanece NP-Difícil, mas um algoritmo de parâmetro fixo é conhecido. Na verdade, o problema tem um kernel de tamanho linear em k (Alber, Fellows & Niedermeier 2004), e tempos de execução que são exponencial √k e cúbico em n pode ser obtido através da aplicação de programação dinâmica para uma branch decomposition do kernel (Fomin & Thilikos 2006).
Variantes
A conjectura de Vizing, Conjectura de Vizing, relaciona o número dominação de um produto cartesiano de grafos para o número dominação de seus fatores.
Houve muito trabalho em conjuntos dominantes ligados. Se S é um conjunto dominante ligado, pode-se formar um spanning tree de G em S forma o conjunto de vértices não-folhas da árvore; Inversamente, se T é qualquer árvore geradora em um gráfico com mais de dois vértices, os vértices não-folha de T formam um conjunto dominante ligado. Portanto, encontrar conjuntos dominantes mínimos ligados é equivalente a encontrar spanning trees com o maior número possível de folhas.
Um conjunto total dominante é um conjunto de vértices de tal forma que todos os vértices no grafo (incluindo os vértices no dominante ajustados entre si) têm um vizinho no conjunto dominante. A figura (c) acima mostra que o conjunto dominante que é conectado e um conjunto dominante total; Os exemplos nas figuras (a) e (b) não são.
Uma k-tupla de um conjunto dominante é um conjunto de vértices tal que cada vértice no grafo tem pelo menos k vizinhos do conjunto Um (1+log n)-aproximação de um conjunto mínimo k-tupla dominante pode ser encontrada em tempo polinomial (Klasing & Laforest 2004). Da mesma forma, um k-conjunto dominante é um conjunto de vértices tal que cada vértice que não está no conjunto tem pelo menos k vizinhos do conjunto. Enquanto todo grafo admite um k-conjunto dominante, apenas grafos com grau mínimo k-1 admitem um conjunto dominante com k-tupla. No entanto, mesmo se o grafo admite um conjunto dominante com k-tupla, um conjunto dominante mínimo com k-tupla pode ser k vezes maior do que um conjunto mínimo dominante k para o mesmo grafo (Förster 2013); Uma (1.7+log Δ)-aproximação de um K-conjunto mínimo dominante pode ser encontrado em tempo polinomial.
Uma partição domatic, domatic partition, é uma partição dos vértices em conjuntos disjuntos dominantes. O número domatic é o tamanho máximo de uma partição domatic.
Um Eternal dominating set é uma versão dinâmica de dominação em que um vértice v em um conjunto dominante D é escolhido e substituído por um vizinho u (u is not in D) tal que o D modificado é um conjunto dominante e este processo pode ser repetido sobre qualquer sequência infinita de opções de vértices v.
Software for searching minimum dominating set
Name (alphabetically) |
License | API language | Brief info |
---|---|---|---|
OpenOpt | BSD | Python | Uses NetworkX graphs, can use free and commercial solvers, included / excluded vertices, see its dominating set page for details and examples |
See also
References
- ↑ Escoffier, Bruno; Paschos, Vangelis Th. (2006). «Completeness in approximation classes beyond APX». Theoretical Computer Science. 359 (1-3): 369–377. doi:10.1016/j.tcs.2006.05.023
- ↑ Papadimitriou, Christos H.; Yannakakis, Mihailis (1991). «Optimization, Approximation, and Complexity Classes». Journal of Computer and Systems Sciences. 43 (3): 425–440. doi:10.1016/0022-0000(91)90023-X
- Alber, Jochen; Fellows, Michael R; Niedermeier, Rolf (2004), «Polynomial-time data reduction for dominating set», Journal of the ACM, 51 (3): 363–384, doi:10.1145/990308.990309.
- Allan, Robert B.; Laskar, Renu (1978), «On domination and independent domination numbers of a graph», Discrete Mathematics, 23 (2): 73–76, doi:10.1016/0012-365X(78)90105-X.
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), «Minimum dominating set», A Compendium of NP Optimization Problems.
- Faudree, Ralph; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), «Claw-free graphs — A survey», Discrete Mathematics, 164 (1–3): 87–147, MR 1432221, doi:10.1016/S0012-365X(96)00045-3.
- Fomin, Fedor V.; Grandoni, Fabrizio; Kratsch, Dieter (2009), «A measure & conquer approach for the analysis of exact algorithms», Journal of the ACM, 56 (5): 25:1–32, doi:10.1145/1552285.1552286.
- Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem; Stepanov, Alexey (2008), «Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications», ACM Transactions on Algorithms, 5 (1): 9:1–17, doi:10.1145/1435375.1435384.
- Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), «Dominating sets in planar graphs: branch-width and exponential speed-up», SIAM Journal on Computing, 36 (2): 281, doi:10.1137/S0097539702419649.
- Förster, Klaus-Tycho. (2013), «Approximating Fault-Tolerant Domination in General Graphs», Proc. of the Tenth Workshop on Analytic Algorithmics and Combinatorics ANALCO, ISBN 978-1-61197-254-2, SIAM, pp. 25–32, doi:10.1137/1.9781611973037.4.
- Predefinição:Garey-Johnson, p. 190, problem GT2.
- Grandoni, F. (2006), «A note on the complexity of minimum dominating set», Journal of Discrete Algorithms, 4 (2): 209–214, doi:10.1016/j.jda.2005.03.002.
- Guha, S.; Khuller, S. (1998), «Approximation algorithms for connected dominating sets», Algorithmica, 20 (4): 374–387, doi:10.1007/PL00009201.
- Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998a), Fundamentals of Domination in Graphs, ISBN 0-8247-0033-3, Marcel Dekker, OCLC 37903553.
- Haynes, Teresa W.; Hedetniemi, Stephen; Slater, Peter (1998b), Domination in Graphs: Advanced Topics, ISBN 0-8247-0034-1, Marcel Dekker, OCLC 38201061.
- Hedetniemi, S. T.; Laskar, R. C. (1990), «Bibliography on domination in graphs and some basic definitions of domination parameters», Discrete Mathematics, 86 (1–3): 257–277, doi:10.1016/0012-365X(90)90365-O.
- Klasing, Ralf; Laforest, Christian (2004), «Hardness results and approximation algorithms of k-tuple domination in graphs», Information Processing Letters, 89 (2): 75–83, doi:10.1016/j.ipl.2003.10.004.
- Kann, Viggo (1992), On the Approximability of NP-complete Optimization Problems (PDF). PhD thesis, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm.
- Raz, R.; Safra, S. (1997), «A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP», Proc. 29th Annual ACM Symposium on Theory of Computing, ISBN 0-89791-888-6, ACM, pp. 475–484, doi:10.1145/258533.258641.
- Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), «Linear-time computability of combinatorial problems on series-parallel graphs», Journal of the ACM, 29 (3): 623–641, doi:10.1145/322326.322328.
- van Rooij, J. M. M.; Nederlof, J.; van Dijk, T. C. (2009), «Inclusion/Exclusion Meets Measure and Conquer: Exact Algorithms for Counting Dominating Sets», Proc. 17th Annual European Symposium on Algorithms, ESA 2009, ISBN 978-3-642-04127-3, Lecture Notes in Computer Science, 5757, Springer, pp. 554–565, doi:10.1007/978-3-642-04128-0_50.