Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903509 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Arman Boyacı, Jérôme Monnot,