Name
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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.endm.2017.10.030 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Maximum weighted minimal dominating set (WUDS),NP-hard,inapproximability,planar bipartite,split graphs,UDS in regular graphs | Discrete mathematics,Graph,Dominating set,Combinatorics,Bipartite graph,Cardinality,Domination analysis,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
62 | 1571-0653 | 1 |
PageRank | References | Authors |
0.36 | 4 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arman Boyaci | 1 | 6 | 4.22 |
| Jérôme Monnot | 2 | 512 | 55.74 |