Title of article
A Polynomial-time Algorithm for the Dominating Induced Matching Problem in the Class of Convex Graphs
Author/Authors
Korpelainen، نويسنده , , Nicholas، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
8
From page
133
To page
140
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.
Keywords
Dominating induced matching , Polynomial-time algorithm , Efficient edge dominating set
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2009
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455012
Link To Document