Abstract | ||
---|---|---|
Independent domination is one of the rare problems for which the complexity of weighted and unweighted versions is known to be different in some classes of graphs. In the present paper, we prove two NP-hardness results, one for the weighted version and one for unweighted, which tighten the gap between them. We also prove that both versions of the problem can be solved in polynomial time for $(P_5,bar{P}_5)$-free graphs generalizing some of the previously known results. |
Year | Venue | Field |
---|---|---|
2016 | arXiv: Discrete Mathematics | Graph,Discrete mathematics,Combinatorics,Generalization,Domination analysis,Time complexity,Mathematics |
DocType | Volume | Citations |
Journal | abs/1602.09124 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vadim V. Lozin | 1 | 947 | 83.65 |
Raffaele Mosca | 2 | 279 | 29.32 |
Victor Zamaraev | 3 | 18 | 9.64 |