O(n) Time Algorithms for Dominating Induced Matching Problems

MIN CHIH LIN; MICHEL MIZRAHI; JAYME L. SZWARCFITER

Montevideo

Conferencia; LATIN 2014 (11th Latin American Theoretical Informatics Symposium); 2014

Universidad de la República

We describe $O(n)$ time algorithms for finding the minimumweighted dominating induced matching of chordal, dually chordal,biconvex, and claw-free graphs. For the first three classes, weprove tight $O(n)$ bounds on the maximum number of edges that agraph having a dominating induced matching may contain. Byapplying these bounds, countings and employing existing $O(n+m)$time algorithms we show that they can be reduced to $O(n)$ time.For claw--free graphs, we describe an algorithm based on that by Cardoso, Korpelainen and Lozin cite{Do-Lo}, for solving the unweighted version of the problem, whichdecreases its complexity from $O(n^2)$ to $O(n)$, whileadditionally solving the weighted version.