Advanced search
Start date
Betweenand
Conteúdos relacionados
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Coelho, Rafael S. [1] ; Moura, Phablo F. S. [1] ; Wakabayashi, Yoshiko [1]
Total Authors: 3
Affiliation:
[1] Univ Sao Paulo, Inst Matemat & Estat, Sao Paulo - Brazil
Total Affiliations: 1
Document type: Journal article
Source: JOURNAL OF COMBINATORIAL OPTIMIZATION; v. 34, n. 4, p. 1060-1083, NOV 2017.
Web of Science Citations: 1
Abstract

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)

FAPESP's process: 13/03447-6 - Combinatorial Structures, Optimization, and Algorithms in Theoretical Computer Science
Grantee:Carlos Eduardo Ferreira
Support Opportunities: Research Projects - Thematic Grants
FAPESP's process: 15/11930-4 - Graph partitioning problems
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships abroad - Research Internship - Doctorate
FAPESP's process: 13/19179-0 - Optimization problems on graph partitioning
Grantee:Phablo Fernando Soares Moura
Support Opportunities: Scholarships in Brazil - Doctorate