Exact Algorithms for Dominating Induced Matching Based on Graph Partition

Mingyu Xiao, Hiroshi Nagamochi

A dominating induced matching, also called an efficient edge domination, of a graph $G=(V,E)$ with $n=|V|$ vertices and $m=|E|$ edges is a subset $F\subseteq E$ of edges in the gr…