Labeling algorithms for domination problems in sun-free chordal graphs
Journal
Discrete Applied Mathematics
Journal Volume
22
Journal Issue
1
Pages
21-34
Date Issued
1988
Author(s)
Abstract
A k-dominating set of a graph G=(V,E) is a set of vertices D such that for every vertex x in V there exists some vertex y in D satisfying d(x,y)≤k. A k-dominating set D of G is connected if the subgraph G[D] induced by D is connected and total if G[D] has no isolated vertex. This paper presents efficient algorithms for finding a minimum cardinality k-dominating set without taking power, connected k-dominating set and total 1-dominating set of a sun-free chordal graph. NP-complete results for these problems are also discussed. © 1988.
Type
journal article