On efficient domination for some classes of \(H\)-free bipartite graphs
From MaRDI portal
Publication:2334041
DOI10.1016/j.dam.2019.06.004zbMath1426.05125arXiv1806.00386OpenAlexW2963101151MaRDI QIDQ2334041
Raffaele Mosca, Andreas Brandstädt
Publication date: 6 November 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1806.00386
polynomial time algorithmNP-completenessclique-widthweighted efficient domination\(H\)-free bipartite 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
- On factorial properties of chordal bipartite graphs
- Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
- The Dilworth number of auto-chordal bipartite graphs
- Recognizing graphs without asteroidal triples
- Classifying the clique-width of \(H\)-free bipartite graphs
- On diameters and radii of bridged graphs
- Generalized domination and efficient domination in graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Weighted efficient domination problem on some perfect graphs
- Polynomial-time algorithm for weighted efficient domination problem on diameter three planar graphs
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Chordal bipartite graphs of bounded tree- and clique-width
- Bipartite graphs without a skew star
- Linear time solvable optimization problems on graphs of bounded clique-width
- Perfect codes in graphs
- Efficient domination and efficient edge domination: a brief survey
- New Polynomial Cases of the Weighted Efficient Domination Problem
- Weighted Efficient Domination for $P_5$-Free and $P_6$-Free Graphs
- A characterization of graphs without long induced paths
- On graphs with polynomially solvable maximum-weight clique problem
- Graph Classes: A Survey
- Reducibility among Combinatorial Problems
- Hereditary Efficiently Dominatable Graphs
- Independent Sets of Maximum Weight in Apple-Free Graphs
This page was built for publication: On efficient domination for some classes of \(H\)-free bipartite graphs
