• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tesis Doctoral
DOI
10.11606/T.45.2017.tde-27062017-101521
Documento
Autor
Nombre completo
Rafael Santos Coelho
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2017
Director
Tribunal
Wakabayashi, Yoshiko (Presidente)
Campêlo Neto, Manoel Bezerra
Gruber, Aritanan Borges Garcia
Lee, Orlando
Rey, Mário Leston
Título en inglés
The k-hop connected dominating set problem: approximation algorithms and hardness results
Palabras clave en inglés
Approximation algorithms
Computational complexity
Inapproximability threshold
K-disruptive separator
K-hop connected dominating set
Polyhedra
Resumen en inglés
Let G be a connected graph and k be a positive integer. A vertex subset D of G is a k-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 (Mink-CDS). We prove that Mink-CDS is NP-hard on planar bipartite graphs of maximum degree 4. We also prove that Mink-CDS is APX-complete on bipartite graphs of maximum degree 4. We present inapproximability thresholds for Mink-CDS on bipar- tite 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 complex- ity of computing this graph parameter. On the positive side, we show an approximation algorithm for Mink-CDS. When k = 1, we present two new approximation algorithms for the weighted version of the problem, one of them restricted to graphs with a poly- nomially bounded number of minimal separators. Finally, also for the weighted variant of the problem where k = 1, we discuss an integer linear programming formulation and conduct a polyhedral study of its associated polytope.
Título en portugués
O problema do conjunto dominante conexo com k-saltos: aproximação e complexidade
Palabras clave en portugués
Algoritmos de aproximação
Complexidade computacional
Conjunto dominante conexo de k-saltos
Limiar de inaproximabilidade
Poliedro
Separador k-disruptivo minimal
Resumen en portugués
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.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tese.pdf (966.80 Kbytes)
Fecha de Publicación
2017-08-29
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2020. Todos los derechos reservados.