On the complexity of the dominating induced matching problem in hereditary classes of graphs
type: Item
instance of: scholarly article
title: On the complexity of the dominating induced matching problem in hereditary classes of graphs
zbMATH Open document ID: 1213.05206
author: Nicholas Korpelainen
author: Vadim Lozin
author: D. M. Cardoso
published in: Discrete Applied Mathematics
publication date: 2011-04-19T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5880189
zbMATH Keywords: dominating induced matching
zbMATH Keywords: efficient edge dominating set
zbMATH Keywords: polynomial-time algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2010.03.011
OpenAlex ID: W1978626345
cites work: On easy and hard hereditary classes of graphs with respect to the independent set problem
cites work: NP-hard graph problems and boundary classes of graphs
cites work: Boundary classes of graphs for the dominating set problem
cites work: Q4425939
cites work: The induced matching and chain subgraph cover problems for convex bipartite graphs
cites work: Graph Classes: A Survey
cites work: Q5463359
cites work: Efficient edge domination in regular graphs
cites work: Dominating Induced Matchings
cites work: Induced matchings
cites work: Induced matchings in intersection graphs.
cites work: Finding a maximum induced matching in weakly chordal graphs
cites work: Induced matchings in asteroidal triple-free graphs
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: Irredundancy in circular arc graphs
cites work: New results on induced matchings
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: Efficient edge domination problems in graphs
cites work: 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
cites work: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs
cites work: Regular codes in regular graphs are difficult
cites work: On maximum induced matchings in bipartite graphs
cites work: Some results on graphs without long induced paths
cites work: On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
cites work: Perfect edge domination and efficient edge domination in graphs
cites work: Solving the weighted efficient edge domination problem on bipartite permutation graphs
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
DOI: 10.1016/J.DAM.2010.03.011
description: scientific article; zbMATH DE number 5880189