Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420100 | Discrete Applied Mathematics | 2011 | 11 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Domingos M. Cardoso, Nicholas Korpelainen, Vadim V. Lozin,