More results on weighted independent domination



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.

[img] 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