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:
| Autores principales: | Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. |
|---|---|
| Formato: | SER |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_Lin |
| Aporte de: |
Ejemplares similares
-
Fast algorithms for some dominating induced matching problems
por: Lin, M.C., et al. -
O(n) time algorithms for dominating induced matching problems
Publicado: (2014) -
Fast algorithms for some dominating induced matching problems
Publicado: (2014) -
An O*(1.1939n) time algorithm for minimum weighted dominating induced matching
por: Lin, M.C., et al. -
Exact Algorithms for Minimum Weighted Dominating Induced Matching
por: Lin, M.C., et al.