Artículo
Approximating weighted induced matchings
Fecha de publicación:
03/2018
Editorial:
Elsevier Science
Revista:
Discrete Applied Mathematics
ISSN:
0166-218X
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
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 K_{1,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 (K_{1,k}, chair)-free graphs.
Palabras clave:
APPROXIMATION ALGORITHMS
,
MAXIMUM INDUCED MATCHING
Archivos asociados
Licencia
Identificadores
Colecciones
Articulos(OCA CIUDAD UNIVERSITARIA)
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Articulos de OFICINA DE COORDINACION ADMINISTRATIVA CIUDAD UNIVERSITARIA
Citación
Lin, Min Chih; Mestre, Julián; Vassiliev, Saveli; Approximating weighted induced matchings; Elsevier Science; Discrete Applied Mathematics; 243; 3-2018; 304-310
Compartir