Lozin, Vadim, Malyshev, Dmitriy, Mosca, Raffaele and Zamaraev, Viktor ORCID: 0000-0001-5755-4141
(2017)
More results on weighted independent domination.
THEORETICAL COMPUTER SCIENCE, 700.
pp. 63-74.
Text
1602.09124v2.pdf - Submitted version Download (214kB) | Preview |
Abstract
Weighted independent domination is an NP-hard graph problem, which remains computationally intractable in many restricted graph classes. In particular, the problem is NP-hard in the classes of sat-graphs and chordal graphs. We strengthen these results by showing that the problem is NP-hard in a proper subclass of the intersection of sat-graphs and chordal graphs. On the other hand, we identify two new classes of graphs where the problem admits polynomial-time solutions.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Independent domination, Polynomial-time algorithm |
Depositing User: | Symplectic Admin |
Date Deposited: | 07 Sep 2020 08:03 |
Last Modified: | 18 Jan 2023 23:35 |
DOI: | 10.1016/j.tcs.2017.08.007 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3100228 |