On the complexity of the dominating induced matching problem in hereditary classes of graphs

Cardoso, Domingos M.; Korpelainen, Nicholas and Lozin, Vadim V. (2011). On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics, 159(7) pp. 521–531.

DOI: https://doi.org/10.1016/j.dam.2010.03.011

Abstract

The dominating induced matching problem, also known as efficient edge domination, is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This problem is known to be NP-complete. We study the computational complexity of the problem in special graph classes. In the present paper, we identify a critical class for this problem (i.e., a class lying on a “boundary” separating difficult instances of the problem from polynomially solvable ones) and derive a number of polynomial-time results. In particular, we develop polynomial-time algorithms to solve the problem for claw-free graphs and convex graphs.

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 38888
• Item Type
• Journal Item
• ISSN
• 0166-218X
• Keywords
• dominating induced matching; efficient edge dominating set; polynomial-time algorithm
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2010 Elsevier B.V.
• Depositing User
• Nicholas Korpelainen