Navegar

Colección

Datos Estadísticas

Artículo

El editor solo permite decargar el artículo en su versión post-print desde el repositorio. Por favor, si usted posee dicha versión, enviela a
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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.

Registro:

Documento: Artículo
Título:On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size
Autor:Lin, M.C.; Mizrahi, M.J.
Filiación:Instituto de Calculo, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Buenos Aires, Argentina
Palabras clave: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
Año:2015
Volumen:197
Página de inicio:53
Página de fin:58
DOI: http://dx.doi.org/10.1016/j.dam.2015.02.010
Título revista:Discrete Applied Mathematics
Título revista abreviado:Discrete Appl Math
ISSN:0166218X
CODEN:DAMAD
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v197_n_p53_Lin

Referencias:

  • Bertossi, A.A., Dominating sets for split and bipartite graphs (1984) Inf. Process. Lett., 19, pp. 37-40
  • Boliac, R., Lozin, V., On the clique-width of graphs in hereditary classes (2002) ISAAC, pp. 44-54
  • Booth, K.S., Johnson, J.H., Dominating sets in chordal graphs (1982) SIAM J. Comput., 11 (1), pp. 191-199
  • Brandstädt, A., Engelfriet, J., Le, H., Lozin, V.V., Clique-width for 4-vertex forbidden subgraphs (2006) Theory Comput. Syst., 39 (4), pp. 561-590
  • Chang, M.-S., Efficient algorithms for the domination problems on interval and circular-arc graphs (1998) SIAM J. Comput., 27, pp. 1671-1694
  • Chao, H.S., Hsu, F.R., Lee, R.C.T., An optimal algorithm for finding the minimum cardinality dominating set on permutation graphs (2000) Discrete Appl. Math., 102 (3), pp. 159-173
  • Cooper, C., Klasing, R., Zito, M., Lower bounds and algorithms for dominating sets in web graphs (2005) Internet Math., 2, pp. 275-300
  • Courcelle, B., Makowsky, J.A., Rotics, U., Linear time solvable optimization problems on graphs of bounded clique width (1999) Theory Comput. Syst., 33, pp. 125-150
  • Dabrowski, K.K., Lozin, V., Raman, R., Ries, B., Colouring vertices of triangle-free graphs without forests (2012) Discrete Math., 312 (7), pp. 1372-1385
  • Farber, M., Domination, independent domination, and duality in strongly chordal graphs (1984) Discrete Appl. Math., 7 (2), pp. 115-130
  • Garey, M.R., Johnson, D.S., (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness, , W. H. Freeman & Co New York, NY, USA
  • Gavril, F., Yannakakis, M., Edge dominating sets in graphs (1980) SIAM J. Appl. Math., 38 (3), pp. 364-372
  • Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Henning, M.A., Domination in graphs applied to electric power networks (2002) SIAM J. Discrete. Math., 15, pp. 519-529
  • Haynes, T.W., Hedetniemi, S.T., Slater, P.J., (1998) Fundamentals of Domination in Graphs
  • Kloks, T., Kratsch, D., Müller, H., Finding and counting small induced subgraphs efficiently (2000) Inf. Process. Lett., 74 (3-4), pp. 115-121
  • Kratsch, D., Domination and total domination on asteroidal triple-free graphs (2000) Discrete Appl. Math., 99 (1-3), pp. 111-123
  • Lozin, V., Milanic, M., (2006) Domination in Graphs of Low Degree. Rutcor Research Report (RRR), , New Jersey 27
  • Matheson, L.R., Tarjan, R.E., Dominating sets in planar graphs (1996) European J. Combin., 17 (6), pp. 565-568
  • Müller, H., Brandstädt, A., The NP-completeness of steiner tree and dominating set for chordal bipartite graphs (1987) Theoret. Comput. Sci., 53, pp. 257-265
  • Nicolai, F., Szymczak, T., Homogeneous sets and domination: A linear time algorithm for distance-hereditary graphs (2001) Networks, 37 (3), pp. 117-128
  • Wu, J., Li, H., A dominating-set-based routing scheme in ad hoc wireless networks (2001) Telecommun. Syst., 18 (1-3), pp. 13-36
  • Yannakakis, M., The complexity of the partial order dimension problem (1982) SIAM J. Algebr. Discrete Methods, 3 (3), pp. 351-358
  • Zverovich, I.E., The domination number of (K <inf>p</inf>, P <inf>5</inf>) -free graphs (2003) Australas. J. Combin., pp. 95-100

Citas:

---------- APA ----------
Lin, M.C. & Mizrahi, M.J. (2015) . On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size. Discrete Applied Mathematics, 197, 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010
---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J. "On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size" . Discrete Applied Mathematics 197 (2015) : 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010
---------- MLA ----------
Lin, M.C., Mizrahi, M.J. "On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size" . Discrete Applied Mathematics, vol. 197, 2015, pp. 53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010
---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J. On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size. Discrete Appl Math. 2015;197:53-58.
http://dx.doi.org/10.1016/j.dam.2015.02.010