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

You can export this page using these formats

About

• Item ORO ID
• 38885
• Item Type
• Conference or Workshop Item
• ISSN
• 1571-0653
• Extra Information
• Paper appears in the proceedings published in Electronic Notes in Discrete Mathematics, 32
• 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
• © 2009 Elsevier B. V.
• Depositing User
• Nicholas Korpelainen