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