On efficient domination for some classes of \(H\)-free chordal graphs
DOI10.1016/j.dam.2019.04.029zbMath1440.05158arXiv1701.03414OpenAlexW2946752364MaRDI QIDQ5918841
Raffaele Mosca, Andreas Brandstädt
Publication date: 29 May 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.03414
2polynomial time algorithmNP-completenessclique-widthweighted efficient domination\( S_{1\(H\)-free chordal graphs3}\)-free chordal graphsextended-gem-free chordal graphsnet-free chordal graphs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- Algorithms for unipolar and generalized split graphs
- Satgraphs and independent domination. I
- Generalized domination and efficient domination in graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
- Weighted efficient domination problem on some perfect graphs
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Weighted independent perfect domination on cocomparability graphs
- The weighted perfect domination problem and its variants
- Linear time solvable optimization problems on graphs of bounded clique-width
- Efficient domination for classes of \(P_6\)-free graphs
- Perfect codes in graphs
- Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time
- New Polynomial Cases of the Weighted Efficient Domination Problem
- Weighted Efficient Domination for $$P_6$$ -Free and for $$P_5$$ -Free Graphs
- Graph Classes: A Survey
- Independence and Efficient Domination on P6-free Graphs
- Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
- Reducibility among Combinatorial Problems
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
- Hereditary Efficiently Dominatable Graphs
- Bounding the Clique‐Width of H‐Free Chordal Graphs
This page was built for publication: On efficient domination for some classes of \(H\)-free chordal graphs