More results on weighted independent domination
From MaRDI portal
Publication:2410364
DOI10.1016/j.tcs.2017.08.007zbMath1378.68088arXiv1602.09124OpenAlexW2618702966MaRDI QIDQ2410364
Vadim V. Lozin, Raffaele Mosca, Victor Zamaraev, Dmitriy S. Malyshev
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Related Items
Independent domination versus weighted independent domination, Weighted Upper Edge Cover: Complexity and Approximability
Cites Work
- Unnamed Item
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- On algorithms for (\(P_5\), gem)-free graphs
- Satgraphs and independent domination. I
- Domination in convex and chordal bipartite graphs
- An algorithm for finding clique cut-sets
- Independent domination in chordal graphs
- Modular decomposition and transitive orientation
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- Independent domination in finitely defined classes of graphs
- New results on weighted independent domination
- The weighted independent domination problem is NP-complete for chordal graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Independent domination in finitely defined classes of graphs: polynomial algorithms
- On graphs with polynomially solvable maximum-weight clique problem
- Edge Dominating Sets in Graphs
- Independent Set in P5-Free Graphs in Polynomial Time
