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...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Lin, Min Chih
Publicado: 2015
Materias:
Algorithms
Complexity
Dominating set
Forbidden induced subgraphs
Computational complexity
Polynomial approximation
Dominating set problems
Dominating sets
Domination problem
Maximum degree
Minimum dominating set
Polynomial-time algorithms
Graph theory
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v197_n_p53_Lin
http://hdl.handle.net/20.500.12110/paper_0166218X_v197_n_p53_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

Ejemplares similares

Ejemplares similares