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

Descripción completa

Guardado en:
Detalles Bibliográficos
Publicado: 2018
Materias:
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
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v243_n_p304_Lin
http://hdl.handle.net/20.500.12110/paper_0166218X_v243_n_p304_Lin
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_0166218X_v243_n_p304_Lin
record_format dspace
spelling paper:paper_0166218X_v243_n_p304_Lin2023-06-08T15:15:35Z Approximating weighted induced matchings 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. 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v243_n_p304_Lin 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
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.
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
publishDate 2018
url https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_0166218X_v243_n_p304_Lin
http://hdl.handle.net/20.500.12110/paper_0166218X_v243_n_p304_Lin
_version_ 1768546624492011520

Ejemplares similares