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

Look up in Google Scholar
No digital document available to download for this item

Item Actions

Export

About

CORE (COnnecting REpositories)