Linear algorithms on Steiner domination of trees

Abstract

A set of vertices $W$ in a connected graph $G$ is called a Steiner dominating set if $W$ is both Steiner and dominating set. The Steiner domination number ${\gamma }_{st}(G)$ is the minimum cardinality of a Steiner dominating set of $G$. A linear algorithm is proposed in this paper for finding a minimum Steiner dominating set for a tree $T$.