Mostrar el registro sencillo del ítem
dc.contributor.author
Lin, Min Chih
dc.contributor.author
Mestre, Julián
dc.contributor.author
Vassiliev, Saveli
dc.date.available
2019-12-26T17:53:53Z
dc.date.issued
2018-03
dc.identifier.citation
Lin, Min Chih; Mestre, Julián; Vassiliev, Saveli; Approximating weighted induced matchings; Elsevier Science; Discrete Applied Mathematics; 243; 3-2018; 304-310
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/92957
dc.description.abstract
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.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
APPROXIMATION ALGORITHMS
dc.subject
MAXIMUM INDUCED MATCHING
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.subject.classification
Ciencias de la Computación
dc.subject.classification
Ciencias de la Computación e Información
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
dc.title
Approximating weighted induced matchings
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2019-12-16T19:12:02Z
dc.journal.volume
243
dc.journal.pagination
304-310
dc.journal.pais
Países Bajos
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Lin, Min Chih. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina
dc.description.fil
Fil: Mestre, Julián. University of Sydney; Australia
dc.description.fil
Fil: Vassiliev, Saveli. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina
dc.journal.title
Discrete Applied Mathematics
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0166218X18300532
Archivos asociados