A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs

Korpelainen, Nicholas (2009). A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. In: Electronic Notes in Discrete Mathematics, Elsevier, 32 pp. 133–140.

URL: http://dx.doi.org/10.1016/j.endm.2009.02.018

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.

Viewing alternatives

Item Actions

Export

About

Recommendations