Navegar

Colección

Datos Estadísticas

Artículo

Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L. "O(n) time algorithms for dominating induced matching problems" (2014) 11th Latin American Theoretical Informatics Symposium, LATIN 2014. 8392 LNCS:399-408
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 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, countings 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 an algorithm based on that by Cardoso, Korpelainen and Lozin [4], for solving the unweighted version of the problem, which decreases its complexity from O(n 2) to O(n), while additionally solving the weighted version. © 2014 Springer-Verlag Berlin Heidelberg.

Registro:

Documento: Artículo
Título:O(n) time algorithms for dominating induced matching problems
Autor:Lin, M.C.; Mizrahi, M.J.; Szwarcfiter, J.L.
Ciudad:Montevideo
Filiación:CONICET, Instituto de Cálculo and Departamento de Computació, Universidad de Buenos Aires, Buenos Aires, Argentina
I. Mat., COPPE and NCE, Universidade Federal Do Rio de Janeiro, Rio de Janeiro, Brazil
Palabras clave:algorithms; dominating induced matchings; graph theory; Algorithms; Information science; Claw-free graphs; Induced matchings; Time algorithms; Graph theory
Año:2014
Volumen:8392 LNCS
Página de inicio:399
Página de fin:408
DOI: http://dx.doi.org/10.1007/978-3-642-54423-1_35
Título revista:11th Latin American Theoretical Informatics Symposium, LATIN 2014
Título revista abreviado:Lect. Notes Comput. Sci.
ISSN:03029743
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8392LNCS_n_p399_Lin

Referencias:

  • Brandstädt, A., Hundt, C., Nevries, R., Efficient edge domination on hole-free graphs in polynomial time (2010) LATIN 2010. LNCS, 6034, pp. 650-661. , López-Ortiz, A. (ed.) Springer, Heidelberg
  • Brandstädt, A., Leitert, A., Rautenbach, D., Efficient dominating and edge dominating sets for graphs and hypergraphs (2012) ISAAC 2012. LNCS, 7676, pp. 267-277. , Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) Springer, Heidelberg
  • Brandstädt, A., Mosca, R., Dominating induced matchings for P7-free Graphs in linear time (2011) ISAAC 2011. LNCS, 7074, pp. 100-109. , Asano, T., Nakano, S.-I., Okamoto, Y., Watanabe, O. (eds.) Springer, Heidelberg
  • Cardoso, D.M., Korpelainen, N., Lozin, V.V., On the complexity of the dominating induced matching problem in hereditary classes of graphs (2011) Discrete Applied Mathematics, 159, pp. 21-531
  • Chen, Z.-Z., Zhang, S., Tight upper bound on the number of edges in a bipartite K3, 3-free or K5-free graph with an application (2002) Information Processing Letters, 84, pp. 141-145
  • Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D., Efficient edge domination problems in graphs (1993) Information Processing Letters, 48, pp. 221-228
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., Exact algorithms for dominating induced matchings (2013) CoRR, abs/1301.7602
  • Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L., An O (1.1939n) time algorithm for minimum weighted dominating induced matching (2013) Algorithms and Computation. LNCS, 8283, pp. 558-567. , Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Springer, Heidelberg
  • Lu, C.L., Ko, M.-T., Tang, C.Y., Perfect edge domination and efficient edge domination in graphs (2002) Discrete Applied Mathematics, 119, pp. 227-250
  • Lu, C.L., Tang, C.Y., Solving the weighted efficient edge domination problem on bipartite permutation graphs (1998) Discrete Applied Mathematics, 87, pp. 203-211A4 - Agencia Nacional de Investigacion e Innovacion (ANII); Centro Latinoamericano de Estudios en Informatica (CLEI); et al.; Google; Universidad de la Republica, CSIC; Yahoo! Labs

Citas:

---------- APA ----------
Lin, M.C., Mizrahi, M.J. & Szwarcfiter, J.L. (2014) . O(n) time algorithms for dominating induced matching problems. 11th Latin American Theoretical Informatics Symposium, LATIN 2014, 8392 LNCS, 399-408.
http://dx.doi.org/10.1007/978-3-642-54423-1_35
---------- CHICAGO ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "O(n) time algorithms for dominating induced matching problems" . 11th Latin American Theoretical Informatics Symposium, LATIN 2014 8392 LNCS (2014) : 399-408.
http://dx.doi.org/10.1007/978-3-642-54423-1_35
---------- MLA ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. "O(n) time algorithms for dominating induced matching problems" . 11th Latin American Theoretical Informatics Symposium, LATIN 2014, vol. 8392 LNCS, 2014, pp. 399-408.
http://dx.doi.org/10.1007/978-3-642-54423-1_35
---------- VANCOUVER ----------
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. O(n) time algorithms for dominating induced matching problems. Lect. Notes Comput. Sci. 2014;8392 LNCS:399-408.
http://dx.doi.org/10.1007/978-3-642-54423-1_35