Thèse de Doctorat
DOI
https://doi.org/10.11606/T.45.2017.tde-27062017-101521
Document
Auteur
Nom complet
Rafael Santos Coelho
Unité de l'USP
Domain de Connaissance
Date de Soutenance
Editeur
São Paulo, 2017
Directeur
Jury
Wakabayashi, Yoshiko (Président)
Campêlo Neto, Manoel Bezerra
Gruber, Aritanan Borges Garcia
Lee, Orlando
Rey, Mário Leston
Titre en anglais
The k-hop connected dominating set problem: approximation algorithms and hardness results
Mots-clés en anglais
Approximation algorithms
Computational complexity
Inapproximability threshold
K-disruptive separator
K-hop connected dominating set
Polyhedra
Resumé en anglais
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.
Titre en portugais
O problema do conjunto dominante conexo com k-saltos: aproximação e complexidade
Mots-clés en portugais
Algoritmos de aproximação
Conjunto dominante conexo de k-saltos
Poliedro