Article ID Journal Published Year Pages File Type
4652575 Electronic Notes in Discrete Mathematics 2009 8 Pages PDF
Abstract

The dominating induced matching problem is the problem of determining whether a graph has an induced matching that dominates every edge of the graph. This is known to be NP-complete in general. We develop a polynomial-time algorithm to solve the problem for convex graphs.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs