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

id	paper:paper_0166218X_v197_n_p53_Lin
record_format	dspace
spelling	paper:paper_0166218X_v197_n_p53_Lin2023-06-08T15:15:34Z On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size Lin, Min Chih Algorithms Complexity Dominating set Forbidden induced subgraphs Algorithms Computational complexity Polynomial approximation Complexity Dominating set problems Dominating sets Domination problem Forbidden induced subgraphs Maximum degree Minimum dominating set Polynomial-time algorithms Graph theory 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-Hardness proof or a polynomial time algorithm. We also extend the results by showing that dominating set problem remains NP-hard even when the graph has maximum degree three, it is planar and has no induced claw, induced diamond, induced K4 nor induced cycle of length 4, 5, 7, 8, 9, 10 and 11. © 2015 Elsevier B.V. All rights reserved. Fil:Lin, M.C. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 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
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Algorithms Complexity Dominating set Forbidden induced subgraphs Algorithms Computational complexity Polynomial approximation Complexity Dominating set problems Dominating sets Domination problem Forbidden induced subgraphs Maximum degree Minimum dominating set Polynomial-time algorithms Graph theory
spellingShingle	Algorithms Complexity Dominating set Forbidden induced subgraphs Algorithms Computational complexity Polynomial approximation Complexity Dominating set problems Dominating sets Domination problem Forbidden induced subgraphs Maximum degree Minimum dominating set Polynomial-time algorithms Graph theory Lin, Min Chih On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
topic_facet	Algorithms Complexity Dominating set Forbidden induced subgraphs Algorithms Computational complexity Polynomial approximation Complexity Dominating set problems Dominating sets Domination problem Forbidden induced subgraphs Maximum degree Minimum dominating set Polynomial-time algorithms Graph theory
description	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-Hardness proof or a polynomial time algorithm. We also extend the results by showing that dominating set problem remains NP-hard even when the graph has maximum degree three, it is planar and has no induced claw, induced diamond, induced K4 nor induced cycle of length 4, 5, 7, 8, 9, 10 and 11. © 2015 Elsevier B.V. All rights reserved.
author	Lin, Min Chih
author_facet	Lin, Min Chih
author_sort	Lin, Min Chih
title	On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_short	On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_full	On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_fullStr	On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_full_unstemmed	On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
title_sort	on the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
publishDate	2015
url	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
work_keys_str_mv	AT linminchih onthecomplexityoftheminimumdominationproblemrestrictedbyforbiddeninducedsubgraphsofsmallsize
_version_	1768546535904116736

On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size

Ejemplares similares