The k-hop connected dominating set problem: approximation algorithms and hardness results (2017)
- Authors:
- Autor USP: COELHO, RAFAEL SANTOS - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/T.45.2017.tde-27062017-101521
- Subjects: OTIMIZAÇÃO COMBINATÓRIA; ALGORITMOS; TEORIA DOS GRAFOS
- Keywords: Algoritmos de aproximação; Approximation algorithms; Complexidade computacional; Computational complexity; Conjunto dominante conexo de k-saltos; Inapproximability threshold; K-disruptive separator; K-hop connected dominating set; Limiar de inaproximabilidade; Poliedro; Polyhedra; Separador k-disruptivo minimal
- Agências de fomento:
- Language: Inglês
- Abstract: Seja G um grafo conexo e k um inteiro positivo. Um subconjunto D de vértices de G é um conjunto dominante conexo de k-saltos se o subgrafo de G induzido por D é conexo e se, para todo vértice v em G, existe um vértice u em D a uma distância não maior do que k de v. Estudamos neste trabalho o problema de se encontrar um conjunto dominante conexo de k-saltos com cardinalidade mínima (Mink-CDS). Provamos que Mink-CDS é NP-difícil em grafos planares bipartidos com grau máximo 4. Mostramos que Mink-CDS é APX-completo em grafos bipartidos com grau máximo 4. Apresentamos limiares de inaproximabilidade para Mink-CDS para grafos bipartidos e (1, 2)-split, sendo que um desses é expresso em função de um parâmetro independente da ordem do grafo. Também discutimos a complexidade computacional do problema de se computar tal parâmetro. No lado positivo, propomos um algoritmo de aproximação para Mink-CDS cuja razão de aproximação é melhor do que a que se conhecia para esse problema. Finalmente, quando k = 1, apresentamos dois novos algoritmos de aproximação para a versão do problema com pesos nos vértices, sendo que um deles restrito a classes de grafos com um número polinomial de separadores minimais. Além disso, discutimos uma formulação de programação linear inteira para essa versão do problema e provamos resultados poliédricos a respeito de algumas das desigualdades que constituem o politopo associado à formulação
- Imprenta:
- Data da defesa: 13.06.2017
- Status:
- Artigo publicado em periódico de acesso aberto (Gold Open Access)
- Versão do Documento:
- Versão publicada (Published version)
- Acessar versão aberta:
-
ABNT
COELHO, Rafael Santos. The k-hop connected dominating set problem: approximation algorithms and hardness results. 2017. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2017. Disponível em: https://teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/. Acesso em: 10 abr. 2026. -
APA
Coelho, R. S. (2017). The k-hop connected dominating set problem: approximation algorithms and hardness results (Tese (Doutorado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/ -
NLM
Coelho RS. The k-hop connected dominating set problem: approximation algorithms and hardness results [Internet]. 2017 ;[citado 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/ -
Vancouver
Coelho RS. The k-hop connected dominating set problem: approximation algorithms and hardness results [Internet]. 2017 ;[citado 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/
Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).
Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
