Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs

In this paper, we consider the r-dominating set problem on graphs which can be generated from the one-vertex graph by a finite number of homogeneous e xtensions and by attaching pendant vertices. We show that for such graphs a minimum cardinality r-dominating set can be computed in O(\V\ \E\) time; f or distance-hereditary graphs-a proper subclass-we even get a linear time a lgorithm. Furthermore, since these graph classes are closed under adding fa lse twins, a total dominating set can be computed in the same time bound. ( C) 2001 John Wiley & Sons, Inc.