Parameterized Algorithms for Total p-Dominating Set
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Total p-Dominating Set is a famous NP-hard problem, and has important applications in wireless networks. In wireless networks, Total p-Dominating Set is usually used to construct the self-protection network for wireless nodes. In this paper, we mainly study the Total p-Dominating Set problem in disk graphs and some more restricted classes of disk graphs from the viewpoint of parameterized complexity and parameterized algorithms. We first prove that Total p-Dominating Set is still NP-hard in unit disk graphs with bounded vertex degree. To gain insight into the source of complexity of Total p-Dominating Set in unit disk graphs, based on parameterized reduction, we further study the parameterized complexity of the considered problem in unit disk graphs. By the method of tree decomposition and dynamic programming, we finally design an exact algorithm with running time O((2p+2)19.1kk3n+n3) for Total p-Dominating Set in planar graphs (a restricted class of disk graphs), where n denotes the number of vertices in the given instance, and k is the size of problem solution.
