The weighted independent domination problem is NP-complete for chordal graphs
From MaRDI portal
Publication:1887072
DOI10.1016/j.dam.2003.05.004zbMath1053.05096OpenAlexW2015322736MaRDI QIDQ1887072
Publication date: 23 November 2004
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2003.05.004
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (13)
More results on weighted independent domination ⋮ Roman domination on strongly chordal graphs ⋮ The weighted independent domination problem: integer linear programming models and metaheuristic approaches ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Independent dominating set problem revisited ⋮ Counting the number of independent sets in chordal graphs ⋮ An optimal algorithm to find minimum k-hop dominating set of interval graphs ⋮ The Weighted Independent Domination Problem: ILP Model and Algorithmic Approaches ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ On the inapproximability of independent domination in \(2P_3\)-free perfect graphs ⋮ Independent domination versus weighted independent domination ⋮ Weighted Upper Edge Cover: Complexity and Approximability ⋮ An optimal algorithm to find minimum k-hop connected dominating set of permutation graphs
Cites Work
This page was built for publication: The weighted independent domination problem is NP-complete for chordal graphs
