Independent domination versus weighted independent domination

DOI10.1016/j.ipl.2020.105914zbMath1478.68250OpenAlexW2999953293WikidataQ126342598 ScholiaQ126342598MaRDI QIDQ2294440

Vadim V. Lozin, Raffaele Mosca, Victor Zamaraev, Dmitriy S. Malyshev

Publication date: 11 February 2020

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://wrap.warwick.ac.uk/132162/1/WRAP-independent-domination-versus-weighted-domination-Lozin-2020.pdf

zbMATH Keywords

NP-hardnesspolynomial-time solvabilityindependent dominationweighted independent domination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Computing weighted subset transversals in \(H\)-free graphs ⋮ Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs

Cites Work

• Satgraphs and independent domination. I
• Domination in convex and chordal bipartite graphs
• Independent domination in chordal graphs
• Independent domination in finitely defined classes of graphs
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• The weighted independent domination problem is NP-complete for chordal graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• More results on weighted independent domination
• Edge Dominating Sets in Graphs

This page was built for publication: Independent domination versus weighted independent domination