A Linear-Time Algorithm for the Weighted Paired-Domination Problem on Block Graphs

Ching-Chi Lin, Cheng-Yu Hsieh

In a graph $G=(V,E)$, a vertex subset $S\subseteq V(G)$ is said to be a dominating set of $G$ if every vertex not in $S$ is adjacent to a vertex in $S$. A dominating set $S$ of $…