Approximating weighted induced matchings
An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ for Δ≥3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the lit...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | JOUR |
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_0166218X_v243_n_p304_Lin |
| Aporte de: |
| id |
todo:paper_0166218X_v243_n_p304_Lin |
|---|---|
| record_format |
dspace |
| spelling |
todo:paper_0166218X_v243_n_p304_Lin2023-10-03T15:03:45Z Approximating weighted induced matchings Lin, M.C. Mestre, J. Vasiliev, S. Approximation algorithms Maximum induced matching Graphic methods Approximation ratios Fractional local ratio Free graphs Greedy algorithms Induced matchings Maximum degree Maximum induced matchings NP Complete Approximation algorithms An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ for Δ≥3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K1,k-free graphs yields an approximation ratio 2k−3. We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to (K1,k,chair)-free graphs. © 2018 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_0166218X_v243_n_p304_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 |
Approximation algorithms Maximum induced matching Graphic methods Approximation ratios Fractional local ratio Free graphs Greedy algorithms Induced matchings Maximum degree Maximum induced matchings NP Complete Approximation algorithms |
| spellingShingle |
Approximation algorithms Maximum induced matching Graphic methods Approximation ratios Fractional local ratio Free graphs Greedy algorithms Induced matchings Maximum degree Maximum induced matchings NP Complete Approximation algorithms Lin, M.C. Mestre, J. Vasiliev, S. Approximating weighted induced matchings |
| topic_facet |
Approximation algorithms Maximum induced matching Graphic methods Approximation ratios Fractional local ratio Free graphs Greedy algorithms Induced matchings Maximum degree Maximum induced matchings NP Complete Approximation algorithms |
| description |
An induced matching is a matching where no two edges are connected by a third edge. Finding a maximum induced matching on graphs with maximum degree Δ for Δ≥3, is known to be NP-complete. In this work we consider the weighted version of this problem, which has not been extensively studied in the literature. We devise an almost tight fractional local ratio algorithm with approximation ratio Δ which proves to be effective also in practice. Furthermore, we show that a simple greedy algorithm applied to K1,k-free graphs yields an approximation ratio 2k−3. We explore the behavior of this algorithm on subclasses of chair-free graphs and we show that it yields an approximation ratio k when restricted to (K1,k,chair)-free graphs. © 2018 Elsevier B.V. |
| format |
JOUR |
| author |
Lin, M.C. Mestre, J. Vasiliev, S. |
| author_facet |
Lin, M.C. Mestre, J. Vasiliev, S. |
| author_sort |
Lin, M.C. |
| title |
Approximating weighted induced matchings |
| title_short |
Approximating weighted induced matchings |
| title_full |
Approximating weighted induced matchings |
| title_fullStr |
Approximating weighted induced matchings |
| title_full_unstemmed |
Approximating weighted induced matchings |
| title_sort |
approximating weighted induced matchings |
| url |
http://hdl.handle.net/20.500.12110/paper_0166218X_v243_n_p304_Lin |
| work_keys_str_mv |
AT linmc approximatingweightedinducedmatchings AT mestrej approximatingweightedinducedmatchings AT vasilievs approximatingweightedinducedmatchings |
| _version_ |
1807321920834633728 |