The weighted independent domination problem is NP-complete for chordal graphs
Journal
Discrete Applied Mathematics
Journal Volume
143
Journal Issue
1-3
Pages
351-352
Date Issued
2004
Author(s)
Abstract
An independent dominating set of a graph G=(V,E) is a pairwise non-adjacent subset D of V such that every vertex not in D is adjacent to at least one vertex in D. Suppose each vertex in V is associated with a weight which is a real number. The weighted independent domination problem is to find an independent domination set of minimum total weights. This paper records an unpublished result of 20 years ago that the weighted independent domination problem is NP-complete for chordal graphs. © 2003 Elsevier B.V. All rights reserved.
SDGs
Type
journal article