On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
We study the computational complexity of the minimum dominating set problem on graphs restricted by forbidden induced subgraphs. We give some dichotomies results for the problem on graphs defined by any combination of forbidden induced subgraphs with at most four vertices, implying either an NP-Hard...
Guardado en:
| Autores principales: | Lin, M.C., Mizrahi, M.J. |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v197_n_p53_Lin |
| Aporte de: |
Ejemplares similares
-
On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
por: Lin, Min Chih
Publicado: (2015) -
Exact Algorithms for Minimum Weighted Dominating Induced Matching
por: Lin, M.C., et al. -
Exact Algorithms for Minimum Weighted Dominating Induced Matching
Publicado: (2017) -
An O*(1.1939n) time algorithm for minimum weighted dominating induced matching
por: Lin, M.C., et al. -
An O*(1.1939n) time algorithm for minimum weighted dominating induced matching
Publicado: (2013)