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
- 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
-
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: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/. Acesso em: 16 fev. 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 http://www.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 fev. 16 ] Available from: http://www.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 fev. 16 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27062017-101521/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
