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 extensions 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; for distance-hereditary graphs-a proper subclass-we even get a linear time algorithm. Furthermore, since these graph classes are closed under adding false twins, a total dominating set can be computed in the same time bound. (C) 2001 John Wiley & Sons, Inc.
distance-hereditary graphs graph algorithms domination problem modular decomposition