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
Publicado: 2014
Materias:
algorithms
dominating induced matchings
graph theory
Algorithms
Information science
Claw-free graphs
Induced matchings
Time algorithms
Graph theory
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8392LNCS_n_p399_Lin
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 paper:paper_03029743_v8392LNCS_n_p399_Lin
record_format dspace
spelling paper:paper_03029743_v8392LNCS_n_p399_Lin2023-06-08T15:28:53Z O(n) time algorithms for dominating induced matching problems 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. 2014 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8392LNCS_n_p399_Lin 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
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.
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
publishDate 2014
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v8392LNCS_n_p399_Lin
http://hdl.handle.net/20.500.12110/paper_03029743_v8392LNCS_n_p399_Lin
_version_ 1768543702879305728

Ejemplares similares