Approximating weighted neighborhood independent sets

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Publicado:	2018
Materias:	Approximation algorithms Graph algorithms Weighted neighborhood independent set Computational complexity Problem solving Approximation ratios Diamond-free graphs General graph Independent set Maximum degree Polynomially solvable Regular graphs Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v130_n_p11_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v130_n_p11_Lin
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_00200190_v130_n_p11_Lin
record_format	dspace
spelling	paper:paper_00200190_v130_n_p11_Lin2023-06-08T14:40:22Z Approximating weighted neighborhood independent sets Approximation algorithms Graph algorithms Weighted neighborhood independent set Approximation algorithms Computational complexity Problem solving Approximation ratios Diamond-free graphs General graph Graph algorithms Independent set Maximum degree Polynomially solvable Regular graphs Graph theory 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 Δ/2+1, 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. © 2017 2018 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v130_n_p11_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v130_n_p11_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 Graph algorithms Weighted neighborhood independent set Approximation algorithms Computational complexity Problem solving Approximation ratios Diamond-free graphs General graph Graph algorithms Independent set Maximum degree Polynomially solvable Regular graphs Graph theory
spellingShingle	Approximation algorithms Graph algorithms Weighted neighborhood independent set Approximation algorithms Computational complexity Problem solving Approximation ratios Diamond-free graphs General graph Graph algorithms Independent set Maximum degree Polynomially solvable Regular graphs Graph theory Approximating weighted neighborhood independent sets
topic_facet	Approximation algorithms Graph algorithms Weighted neighborhood independent set Approximation algorithms Computational complexity Problem solving Approximation ratios Diamond-free graphs General graph Graph algorithms Independent set Maximum degree Polynomially solvable Regular graphs Graph theory
description	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 Δ/2+1, 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. © 2017
title	Approximating weighted neighborhood independent sets
title_short	Approximating weighted neighborhood independent sets
title_full	Approximating weighted neighborhood independent sets
title_fullStr	Approximating weighted neighborhood independent sets
title_full_unstemmed	Approximating weighted neighborhood independent sets
title_sort	approximating weighted neighborhood independent sets
publishDate	2018
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v130_n_p11_Lin http://hdl.handle.net/20.500.12110/paper_00200190_v130_n_p11_Lin
_version_	1768541829415829504

Approximating weighted neighborhood independent sets

Ejemplares similares