Name
Abstract | ||
|---|---|---|
A set D⊆V of a graph G = (V, E) is called a restrained dominating set of G if every vertex not in D is adjacent to a vertex in D and to a vertex in V\D. The Minimum Restrained Domination problem is to find a restrained dominating set of minimum cardinality. The decision version of the Minimum Restrained Domination problem is known to be NP-complete for chordal graphs. In this paper, we strengthen this NP-completeness result by showing that the problem remains NP-complete for doubly chordal graphs, a subclass of chordal graphs. We also propose a polynomial time algorithm to solve the Minimum Restrained Domination problem in block graphs, a subclass of doubly chordal graphs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.endm.2017.11.015 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Domination,Restrained domination,NP-completeness,Chordal graphs,Doubly chordal graphs,Block graphs | Graph,Discrete mathematics,Dominating set,Combinatorics,Vertex (geometry),Subclass,Chordal graph,Cardinality,Time complexity,Mathematics | Journal |
Volume | ISSN | Citations |
63 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arti Pandey | 1 | 3 | 5.47 |
| B. S. Panda | 2 | 99 | 21.18 |