Eu estou trabalhando em algoritmos de aproximação para um problema mínimo de conjunto dominante. Em particular, estou interessado em classes de gráficos restritas por subgráficos induzidos proibidos. Como o problema de dominação e suas variantes foram extensivamente estudados, suponho que alguém possa ter trabalhado nisso antes. Então, a questão é:
Alguém conhece documentos onde são estudados algoritmos de aproximação para problemas de dominação para classes de gráficos definidas por subgráficos induzidos proibidos?
Desde já, obrigado. Atenciosamente.
Respostas:
A classe de gráficos de linha pode ser caracterizada por uma família finita de subgrafos induzidos proibidos (Beineke). Um conjunto dominante em um gráfico de linhas G corresponde a um conjunto dominante de arestas do gráfico raiz de G (e vice-versa), e o tamanho do conjunto dominante de arestas mínimo pode ser aproximado pelo fator 2 em tempo polinomial.
fonte
No gráfico excluindo um menor fixo, por exemplo, gráficos planares, muitos problemas, incluindo cobertura de vértices, conjunto dominante , conjunto dominante de aresta, conjunto dominante de R, conjunto dominante conectado, conjunto dominante de aresta conectado, podem ser bem aproximados (geralmente PTAS ou com fatores constantes) . O documento a seguir pode servir como ponto de partida.
A Teoria da Bidimensionalidade e Suas Aplicações Algorítmicas
fonte
Do mesmo modo que a resposta de Y. Okamoto, há um argumento fácil que mostra que o problema do conjunto dominante admite um algoritmo de aproximação nos induzidos .(ℓ−1) K1,ℓ
De fato, basta pegar qualquer conjunto dominante independente (ou seja, um conjunto independente máximo): temos a cadeia de desigualdades , onde e são o número de dominação e o número de independência de , respectivamente (veja o Lema 1 para uma prova, em particular, da primeira desigualdade).I α(G)ℓ−1≤γ(G)≤I≤α(G) γ(G) α(G) G
fonte