Pure and Applied Mathematics Quarterly
Volume 18 (2022)
Special issue in honor of Fan Chung
Guest editors: Paul Horn, Yong Lin, and Linyuan Lu
A greedy algorithm for the connected positive influence dominating set in $k$-regular graphs
Pages: 2461 – 2478
For a graph $G=(V,E)$, a vertex subset $C \subseteq V$ is a connected positive influence dominating set of $G$ if every node $v$ in $V \setminus C$ has at least a fraction $\rho (0 \lt \rho \lt 1)$ of its neighbors in $C$ and the subgraph of $G$ induced by $C$ is connected. In this paper, let $G$ be a regular graph with degree $k$. We present a greedy algorithm to compute a connected positive influence dominating set in $G$, and it is proved that the approximation ratio of the algorithm is $2 + \ln (k^2 + 2k)$.
connected positive influence dominating set, greedy algorithm, potential function
2010 Mathematics Subject Classification
Primary 05C69. Secondary 68W25, 68W40.
This work was supported by the NSF of China (No. 11971146), by the NSF of Hebei Province (Nos. A2017403010, A2019205089 and A2019205092), and by the Graduate Innovation Grant Program of Hebei Normal University (No. CXZZSS2021045).
Received 25 June 2021
Received revised 28 March 2022
Accepted 5 April 2022
Published 29 March 2023