O(n) time algorithms for dominating induced matching problems
We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may conta...
Guardado en:
| Publicado: |
2014
|
|---|---|
| Materias: | |
| Acceso en línea: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8392LNCS_n_p399_Lin http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_Lin |
| Aporte de: |
| Sumario: | We describe O(n) time algorithms for finding the minimum weighted dominating induced matching of chordal, dually chordal, biconvex, and claw-free graphs. For the first three classes, we prove tight O(n) bounds on the maximum number of edges that a graph having a dominating induced matching may contain. By applying 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 [4], for solving the unweighted version of the problem, which decreases its complexity from O(n 2) to O(n), while additionally solving the weighted version. © 2014 Springer-Verlag Berlin Heidelberg. |
|---|