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

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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2001, Vol.263 (1-2), p.3-8
Main Authors: Yeh, Hong-Gwa, Chang, Gerard J.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. copyright 2001 Elsevier Science B.V. All rights reserved.
ISSN:0304-3975
DOI:10.1016/S0304-3975(00)00225-5