Article ID Journal Published Year Pages File Type
10331898 Information Processing Letters 2015 7 Pages PDF
Abstract
An efficient dominating set (or perfect code) in a graph is a set of vertices the closed neighborhoods of which partition the vertex set of the graph. The minimum weight efficient domination problem is the problem of finding an efficient dominating set of minimum weight in a given vertex-weighted graph; the maximum weight efficient domination problem is defined similarly. We develop a framework for solving the weighted efficient domination problems based on a reduction to the maximum weight independent set problem in the square of the input graph. Using this approach, we improve on several previous results from the literature by deriving polynomial-time algorithms for the weighted efficient domination problems in the classes of dually chordal and AT-free graphs. In particular, this answers a question by Lu and Tang regarding the complexity of the minimum weight efficient domination problem in strongly chordal graphs.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,