On the complexity of the dominating induced matching problem in hereditary classes of graphs
From MaRDI portal
Publication:716179
DOI10.1016/j.dam.2010.03.011zbMath1213.05206OpenAlexW1978626345MaRDI QIDQ716179
Vadim V. Lozin, Nicholas Korpelainen, Domingos Moreira Cardoso
Publication date: 19 April 2011
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2010.03.011
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (22)
Perfect edge domination: hard and solvable cases ⋮ Efficient domination through eigenvalues ⋮ Kernelization of edge perfect code and its variants ⋮ Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time ⋮ Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs ⋮ Modelling and solving the perfect edge domination problem ⋮ On the dominating induced matching problem: spectral results and sharp bounds ⋮ Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time ⋮ Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time ⋮ Dominating induced matchings in graphs without a skew star ⋮ Dominating induced matchings for \(P_7\)-free graphs in linear time ⋮ Combinatorial and spectral properties of König-Egerváry graphs ⋮ Exact algorithms for minimum weighted dominating induced matching ⋮ Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time ⋮ Fast algorithms for some dominating induced matching problems ⋮ Efficient domination for classes of \(P_6\)-free graphs ⋮ Dominating induced matching in some subclasses of bipartite graphs ⋮ Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs ⋮ The Maximum Number of Dominating Induced Matchings ⋮ Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time ⋮ Exact algorithms for dominating induced matching based on graph partition ⋮ Some results on dominating induced matchings
Cites Work
- Unnamed Item
- Unnamed Item
- Irredundancy in circular arc graphs
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Efficient edge domination in regular graphs
- Some results on graphs without long induced paths
- Induced matchings
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Efficient edge domination problems in graphs
- Regular codes in regular graphs are difficult
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Induced matchings in asteroidal triple-free graphs
- Induced matchings in intersection graphs.
- Perfect edge domination and efficient edge domination in graphs
- Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size
- Finding a maximum induced matching in weakly chordal graphs
- On maximum induced matchings in bipartite graphs
- Boundary classes of graphs for the dominating set problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- New results on induced matchings
- NP-hard graph problems and boundary classes of graphs
- A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
- Dominating Induced Matchings
- Graph Classes: A Survey
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
This page was built for publication: On the complexity of the dominating induced matching problem in hereditary classes of graphs
