Back to Search
Start Over
On Complexities of Minus Domination
- Publication Year :
- 2013
-
Abstract
- A function f : V → { − 1 , 0 , 1 } is a minus-domination function of a graph G = ( V , E ) if the values over the vertices in each closed neighborhood sum to a positive number. The weight of f is the sum of f ( x ) over all vertices x ∈ V . In the minus-domination problem, one tries to minimize the weight of a minus-domination function. In this paper, we show that (1) the minus-domination problem is fixed-parameter tractable for d -degenerate graphs when parameterized by the size of the minus-dominating set and by d , where the size of a minus domination is the number of vertices that are assigned 1 , (2) the minus-domination problem is polynomial for graphs of bounded rankwidth and for strongly chordal graphs, (3) it is N P -complete for split graphs, and (4) there is no fixed-parameter algorithm for minus-domination.
- Subjects :
- FOS: Computer and information sciences
Discrete Mathematics (cs.DM)
Applied Mathematics
010102 general mathematics
Degenerate energy levels
Parameterized complexity
0102 computer and information sciences
01 natural sciences
Graph
Theoretical Computer Science
Combinatorics
Computational Theory and Mathematics
010201 computation theory & mathematics
Chordal graph
Bounded function
FOS: Mathematics
Mathematics - Combinatorics
Combinatorics (math.CO)
0101 mathematics
Mathematics
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....801404dee2fff0c7853cd9caf4ce8839