Artículo
Approximating weighted neighborhood independent sets
Fecha de publicación:
02/2018
Editorial:
Elsevier Science
Revista:
Information Processing Letters
ISSN:
0020-0190
Idioma:
Inglés
Tipo de recurso:
Artículo publicado
Clasificación temática:
Resumen
A neighborhood independent set (NI-set) is a subset of edges in a graph such that the closed neighborhood of any vertex contains at most one edge of the subset. Finding a maximum cardinality NI-set is an NP-complete problem. We consider the weighted version of this problem. For general graphs we give an algorithm with approximation ratio Δ, and for diamond-free graphs we give a ratio , where Δ is the maximum degree of the input graph. Furthermore, we show that the problem is polynomially solvable on cographs. Finally, we give a tight upper bound on the cardinality of a NI-set on regular graphs.
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, Julian; Vasiliev, Saveliy; Approximating weighted neighborhood independent sets; Elsevier Science; Information Processing Letters; 130; 2-2018; 11-15
Compartir
Altmétricas