Article ID Journal Published Year Pages File Type
8903509 Electronic Notes in Discrete Mathematics 2017 6 Pages PDF
Abstract
The cardinality of a maximum minimal dominating set of a graph is called its upper domination number. The problem of computing this number is generally NP-hard but can be solved in polynomial time in some restricted graph classes. In this work, we consider the complexity and approximability of the weighted version of the problem in two special graph classes: planar bipartite, split. We also provide an inapproximability result for an unweighted version of this problem in regular graphs.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,