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.011zbMATH Open1213.05206OpenAlexW1978626345MaRDI QIDQ716179FDOQ716179
Authors: Nicholas Korpelainen, Vadim Lozin, D. M. 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
Recommendations
- Dominating induced matchings
- A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
- Dominating induced matchings in graphs containing no long claw
- Dominating induced matching in some subclasses of bipartite graphs
- Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Graph Classes: A Survey
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Boundary classes of graphs for the dominating set problem
- Linear time solvable optimization problems on graphs of bounded clique-width
- NP-hard graph problems and boundary classes of graphs
- On the clique-width of some perfect graph classes
- Some results on graphs without long induced paths
- Induced matchings
- On maximum induced matchings in bipartite graphs
- Induced matchings in asteroidal triple-free graphs
- Efficient edge domination in regular graphs
- Solving the weighted efficient edge domination problem on bipartite permutation graphs
- Efficient edge domination problems in graphs
- Perfect edge domination and efficient edge domination in graphs
- Dominating induced matchings
- 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
- New results on induced matchings
- Induced matchings in intersection graphs.
- Finding a maximum induced matching in weakly chordal graphs
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- The induced matching and chain subgraph cover problems for convex bipartite graphs
- Title not available (Why is that?)
- On the clique-width of graph with few \(P_{4}\)'s
- Regular codes in regular graphs are difficult
- Title not available (Why is that?)
- A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
- Irredundancy in circular arc graphs
Cited In (28)
- Dominating induced matching in some subclasses of bipartite graphs
- Combinatorial and spectral properties of König-Egerváry graphs
- Some results on dominating induced matchings
- Weighted efficient domination for some classes of \(H\)-free and of \((H_1, H_2)\)-free graphs
- Perfect edge domination: hard and solvable cases
- Dominating induced matchings in graphs without a skew star
- Efficient domination through eigenvalues
- Kernelization of edge perfect code and its variants
- A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
- Dominating induced matchings for \(P_7\)-free graphs in linear time
- Finding dominating induced matchings in \(P_9\)-free graphs in polynomial time
- Finding dominating induced matchings in \(S_{2, 2, 3}\)-free graphs in polynomial time
- The Maximum Number of Dominating Induced Matchings
- Finding dominating induced matchings in \(P_{10}\)-free graphs in polynomial time
- Modelling and solving the perfect edge domination problem
- Finding dominating induced matchings in \(S_{1, 1, 5}\)-free graphs in polynomial time
- Dominating induced matching in some subclasses of bipartite graphs
- Dominating induced matchings
- Efficient edge domination on hole-free graphs in polynomial time
- On the dominating induced matching problem: spectral results and sharp bounds
- Dominating induced matchings in graphs containing no long claw
- Graphs whose vertices of degree at least 2 lie in a triangle
- Fast algorithms for some dominating induced matching problems
- Exact algorithms for dominating induced matching based on graph partition
- Exact algorithms for minimum weighted dominating induced matching
- Efficient domination for classes of \(P_6\)-free graphs
- Dominating induced matchings in \(S_{1 , 2 , 4}\)-free graphs
- Finding dominating induced matchings in \(P_8\)-free graphs in polynomial time
This page was built for publication: On the complexity of the dominating induced matching problem in hereditary classes of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q716179)
