An $O^{\ast }(1.1939^n)$ time algorithm for minimum weighted dominating induced matching

Min Chih Lin, Michel J. Mizrahi, Jayme L. Szwarcfiter

Say that an edge of a graph $G$ dominates itself and every other edge adjacent to it. An edge dominating set of a graph $G=(V,E)$ is a subset of edges $E^{\prime }\subseteq E$ which domina…