Mostrar el registro sencillo del ítem
dc.contributor.author
Lin, Min Chih
dc.contributor.author
Vasiliev, Saveliy
dc.date.available
2018-09-13T17:07:47Z
dc.date.issued
2015-09
dc.identifier.citation
Lin, Min Chih; Vasiliev, Saveliy; Approximation algorithms for clique transversals on some graph classes; Elsevier Science; Information Processing Letters; 115; 9; 9-2015; 667-670
dc.identifier.issn
0020-0190
dc.identifier.uri
http://hdl.handle.net/11336/59528
dc.description.abstract
Given a graph G=(V,E) a clique is a maximal subset of pairwise adjacent vertices of V of size at least 2. A clique transversal is a subset of vertices that intersects the vertex set of each clique of G. Finding a minimum-cardinality clique transversal is NP-hard for the following classes: planar, line and bounded degree graphs. For line graphs we present a 3-approximation for the unweighted case and a 4-approximation for the weighted case with nonnegative weights; a ⌈(Δ(G)+1)/2 ⌉(-approximation for bounded degree graphs and a 3-approximation for planar 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-nd/2.5/ar/
dc.subject
Approximation Algorithms
dc.subject
Clique Transversal
dc.subject
Graph Classes
dc.subject
Np-Hard
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
Approximation algorithms for clique transversals on some graph classes
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
2018-09-13T13:12:30Z
dc.journal.volume
115
dc.journal.number
9
dc.journal.pagination
667-670
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: Vasiliev, Saveliy. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina
dc.journal.title
Information Processing Letters
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2015.04.003
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0020019015000630
Archivos asociados
Tamaño:
231.1Kb
Formato:
PDF