Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

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 contain. By applying these bounds, and employing existing O(n+m) time algorithms we show that they can be reduced to O(n) time. For claw-free graphs, we describe a variation of the existing algorithm for solving the unweighted version of the problem, which decreases its complexity from O(n2) to O(n), while additionally solving the weighted version. The same algorithm can be easily modified to count the number of DIM's of the given graph. © 2014 Elsevier B.V.

Registro:

Documento: Artículo
Título:Fast algorithms for some dominating induced matching problems
Autor:Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L.
Filiación:Departamento de Computación, Universidad de Buenos Aires, Argentina
Instituto de Matemática, NCE and COPPE, Universidade Federal Do Rio de Janeiro, Brazil
Instituto Nacional de Metrologia, Qualidade e Tecnologia, Brazil
Palabras clave:Algorithms; Dominating induced matchings; Graph theory; Algorithms; Algorithm for solving; Claw-free graphs; Fast algorithms; Induced matchings; Time algorithms; Graph theory
Año:2014
Volumen:114
Número:10
Página de inicio:524
Página de fin:528
DOI: http://dx.doi.org/10.1016/j.ipl.2014.04.012
Título revista:Information Processing Letters
Título revista abreviado:Inf. Process. Lett.
ISSN:00200190
CODEN:IFPLA
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v114_n10_p524_Lin

Referencias:

  • Brandstädt, A., Hundt, C., Nevries, R., Efficient edge domination on hole-free graphs in polynomial time (2011) LATIN'10 Latin American Conference on Theoretical Informatics, 6034, pp. 650-661. , Lect. Notes Comput. Sci
  • Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) ISAAC'12 International Symposium on Algorithms and Computation, 7676, pp. 267-277. , Lect. Notes Comput. Sci
  • Brandstädt, A., Mosca, R., Dominating induced matchings for P7-free graphs in linear time (2011) ISAAC'11 International Symposium on Algorithms and Computation, 7074, pp. 100-109. , Lect. Notes Comput. Sci
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., (2013) Exact Algorithms for Dominating Induced Matchings, , arxiv:1301.7602 CoRR
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., An O (1.1939 n) time algorithm for minimum weighted dominating induced matching (2013) ISAAC'13 International Symposium on Algorithms and Computation, 8283, pp. 558-567. , Lect. Notes Comput. Sci
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., O (n) time algorithms for dominating induced matching problems (2014) LATIN'14 Latin-American Theoretical Informatics, 8392, pp. 399-408. , Lect. Notes Comput. Sci
  • Cardoso, D.M., Korpelainen, N., Lozin, V.V., On the complexity of the dominating induced matching problem in hereditary classes of graphs (2011) Discrete Appl. Math., 159, pp. 521-531
  • Chen, Z.-Z., Zhang, S., Tight upper bound on the number of edges in a bipartite K 3,3-free or K5-free graph with an application (2002) Inf. Process. Lett., 84, pp. 141-145
  • Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D., Efficient edge domination problems in graphs (1993) Inf. Process. Lett., 48, pp. 221-228
  • Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs (1998) Discrete Appl. Math., 87, pp. 203-211
  • Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Appl. Math., 119, pp. 227-250

Citas:

---------- APA ----------
Lin, M.C., Mizrahi, M.J. & Szwarcfiter, J.L. (2014) . Fast algorithms for some dominating induced matching problems. Information Processing Letters, 114(10), 524-528.
http://dx.doi.org/10.1016/j.ipl.2014.04.012
---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "Fast algorithms for some dominating induced matching problems" . Information Processing Letters 114, no. 10 (2014) : 524-528.
http://dx.doi.org/10.1016/j.ipl.2014.04.012
---------- MLA ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "Fast algorithms for some dominating induced matching problems" . Information Processing Letters, vol. 114, no. 10, 2014, pp. 524-528.
http://dx.doi.org/10.1016/j.ipl.2014.04.012
---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. Fast algorithms for some dominating induced matching problems. Inf. Process. Lett. 2014;114(10):524-528.
http://dx.doi.org/10.1016/j.ipl.2014.04.012