More results on weighted independent domination

DOI10.1016/J.TCS.2017.08.007MaRDI QIDQ2410364zbMATH OpenOpenAlexFDO

Authors Vadim Lozin, Raffaele Mosca, D. S. Malyshev, Victor Zamaraev

Publication date 17 October 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.09124, http://wrap.warwick.ac.uk/92508/7/WRAP-results-weighted-independent-domination-Lozin-2017.pdf

zbMATH Keywords

independent dominationpolynomial-time algorithm

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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.

Recommendations

• New results on weighted independent domination
• The weighted independent domination problem is NP-complete for chordal graphs
• Independent domination versus weighted independent domination
• On domination problems for permutation and other graphs
• Independent domination in hereditary classes

Cites work

• An algorithm for finding clique cut-sets
• Domination in convex and chordal bipartite graphs
• Edge Dominating Sets in Graphs
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• Independent domination in chordal graphs
• Independent domination in finitely defined classes of graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Independent set in P₅-free graphs in polynomial time
• Linear time solvable optimization problems on graphs of bounded clique-width
• Modular decomposition and transitive orientation
• New results on weighted independent domination
• On algorithms for (P₅, gem)-free graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• On graphs with polynomially solvable maximum-weight clique problem
• Satgraphs and independent domination. I
• The weighted independent domination problem is NP-complete for chordal graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs

Cited in

(6)

• The weighted independent domination problem: integer linear programming models and metaheuristic approaches
• New results on weighted independent domination
• The weighted independent domination problem is NP-complete for chordal graphs
• Independent domination versus weighted independent domination
• Weighted upper edge cover: complexity and approximability
• Satgraphs and independent domination. I

This page was built for publication: More results on weighted independent domination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410364)