Homogeneous sets and domination: A linear time algorithm for distance—hereditary graphs
Falk Nicolai, Thomas Szymczak · Networks · 2001
Abstract 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. © 2001 John Wiley & Sons, Inc.