A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
Andreas Brandst�dt, Feodor F. Dragan · Networks · 1998
A distance-hereditary graph is a connected graph in which every induced path is isometric, i.e., the distance of any two vertices in an induced path equals their distance in the graph. We present a linear time labeling algorithm for the minimum cardinality connected r-dominating set and Steiner tree problems on distance-hereditary graphs. © 1998 John Wiley & Sons, Inc. Networks 31: 177–182, 1998