Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

The k-hop connected dominating set problem: approximation and hardness

Texto completo
Autor(es):
Coelho, Rafael S. [1] ; Moura, Phablo F. S. [1] ; Wakabayashi, Yoshiko [1]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Número total de Afiliações: 1
Tipo de documento: Artigo Científico
Fonte: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 34, n. 4, p. 1060-1083, NOV 2017.
Citações Web of Science: 1
Resumo

Let G be a connected graph and kappa be a positive integer. A vertex subset D of G is a kappa-hop connected dominating set if the subgraph of G induced by D is connected, and for every vertex v in G there is a vertex u in D such that the distance between v and u in G is at most k. We study the problem of finding a minimum k-hop connected dominating set of a graph (Min kappa-CDS). We prove that Min kappa-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Min kappa-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Min kappa-CDS on bipartite and on (1, 2)-split graphs. Interestingly, one of these thresholds is a parameter of the input graph which is not a function of its number of vertices. We also discuss the complexity of computing this graph parameter. On the positive side, we show an approximation algorithm for Min kappa-CDS. Finally, when kappa = 1, we present two new approximation algorithms for the weighted version of the problem restricted to graphs with a polynomially bounded number of minimal separators. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 15/11930-4 - Problemas de particionamento em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
Processo FAPESP: 13/19179-0 - Problemas de otimização sobre partição em grafos
Beneficiário:Phablo Fernando Soares Moura
Linha de fomento: Bolsas no Brasil - Doutorado