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.05206MaRDI 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
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
The Maximum Number of Dominating Induced Matchings, Dominating induced matchings for \(P_7\)-free graphs in linear time, Fast algorithms for some dominating induced matching problems, Exact algorithms for dominating induced matching based on graph partition, Dominating induced matchings in graphs without a skew star
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
