Weighted connected k-domination and weighted k-dominating clique in distance-hereditary graphs

Abstract

A graph is distance-hereditary if the distance between any two vertices in a connected induced subgraph is the same as in the original graph. This paper presents efficient algorithms for solving the weighted connected k-domination and the weighted k-dominating clique problems in distance-hereditary graphs, (C) 2001 Elsevier Science B.V. All rights reserved.