Fast algorithms for some 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...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_00200190_v114_n10_p524_Lin |
| Aporte de: |
| id |
todo:paper_00200190_v114_n10_p524_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_00200190_v114_n10_p524_Lin2023-10-03T14:16:39Z Fast algorithms for some dominating induced matching problems Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. Algorithms Dominating induced matchings Graph theory Algorithms Algorithm for solving Claw-free graphs Fast algorithms 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, 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_00200190_v114_n10_p524_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 Algorithm for solving Claw-free graphs Fast algorithms Induced matchings Time algorithms Graph theory |
| spellingShingle |
Algorithms Dominating induced matchings Graph theory Algorithms Algorithm for solving Claw-free graphs Fast algorithms Induced matchings Time algorithms Graph theory Lin, M.C. Mizrahi, M.J. Szwarcfiter, J.L. Fast algorithms for some dominating induced matching problems |
| topic_facet |
Algorithms Dominating induced matchings Graph theory Algorithms Algorithm for solving Claw-free graphs Fast algorithms 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, 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. |
| format |
JOUR |
| 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 |
Fast algorithms for some dominating induced matching problems |
| title_short |
Fast algorithms for some dominating induced matching problems |
| title_full |
Fast algorithms for some dominating induced matching problems |
| title_fullStr |
Fast algorithms for some dominating induced matching problems |
| title_full_unstemmed |
Fast algorithms for some dominating induced matching problems |
| title_sort |
fast algorithms for some dominating induced matching problems |
| url |
http://hdl.handle.net/20.500.12110/paper_00200190_v114_n10_p524_Lin |
| work_keys_str_mv |
AT linmc fastalgorithmsforsomedominatinginducedmatchingproblems AT mizrahimj fastalgorithmsforsomedominatinginducedmatchingproblems AT szwarcfiterjl fastalgorithmsforsomedominatinginducedmatchingproblems |
| _version_ |
1807318378312892416 |