O(n) time algorithms for dominating induced matching problems

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 conta...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.
Formato: SER
Materias:
algorithms
dominating induced matchings
graph theory
Algorithms
Information science
Claw-free graphs
Induced matchings
Time algorithms
Graph theory
Acceso en línea:http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:paper_03029743_v8392LNCS_n_p399_Lin
record_format dspace
spelling todo:paper_03029743_v8392LNCS_n_p399_Lin2023-10-03T15:19:36Z O(n) time algorithms for dominating induced matching problems Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. algorithms dominating induced matchings graph theory Algorithms Information science Claw-free graphs Induced matchings Time algorithms Graph theory 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. SER info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_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
dominating induced matchings
graph theory
Algorithms
Information science
Claw-free graphs
Induced matchings
Time algorithms
Graph theory
spellingShingle algorithms
dominating induced matchings
graph theory
Algorithms
Information science
Claw-free graphs
Induced matchings
Time algorithms
Graph theory
Lin, M.C.
Mizrahi, M.J.
Szwarcfiter, J.L.
O(n) time algorithms for dominating induced matching problems
topic_facet algorithms
dominating induced matchings
graph theory
Algorithms
Information science
Claw-free graphs
Induced matchings
Time algorithms
Graph theory
description 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.
format SER
author Lin, M.C.
Mizrahi, M.J.
Szwarcfiter, J.L.
author_facet Lin, M.C.
Mizrahi, M.J.
Szwarcfiter, J.L.
author_sort Lin, M.C.
title O(n) time algorithms for dominating induced matching problems
title_short O(n) time algorithms for dominating induced matching problems
title_full O(n) time algorithms for dominating induced matching problems
title_fullStr O(n) time algorithms for dominating induced matching problems
title_full_unstemmed O(n) time algorithms for dominating induced matching problems
title_sort o(n) time algorithms for dominating induced matching problems
url http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_Lin
work_keys_str_mv AT linmc ontimealgorithmsfordominatinginducedmatchingproblems
AT mizrahimj ontimealgorithmsfordominatinginducedmatchingproblems
AT szwarcfiterjl ontimealgorithmsfordominatinginducedmatchingproblems
_version_ 1782029537426538496

Ejemplares similares