Weighted connected domination and Steiner trees in distance-hereditary graphs (Q1270785): Difference between revisions

A distance-hereditary graph is a connected graph in which every induced path is isometric, that is, the distance between any two vertices in an induced path equals their distance in the graph. A dominating set of a graph is a set of vertices such that every vertex outside is adjacent to a vertex in the set. The connected domination problem is to find a smallest connected dominating set. The Steiner tree problem is, for a given set \(T\) of target vertices, to find a smallest set \(S\) of vertices such that \(S \cup T\) is connected. Both problems are NP-complete in general. Restricted to distance-hereditary graphs they become solvable in linear time, even if we allow real weights on the vertices. This generalizes earlier work by \textit{A. Brandstädt} and \textit{F. F. Dragan} [Networks 31, No. 3, 177-182 (1998)].