Artículo
Lin, M.C.; Mestre, J.; Vasiliev, S. "Approximating weighted neighborhood independent sets" (2018) Information Processing Letters. 130:11-15
Estamos trabajando para incorporar este artículo al repositorio
Consulte la política de Acceso Abierto del editor
Abstract:
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
Registro:
| Documento: | Artículo |
| Título: | Approximating weighted neighborhood independent sets |
| Autor: | Lin, M.C.; Mestre, J.; Vasiliev, S. |
| Filiación: | CONICET, Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Argentina The University of Sydney, Australia |
| Palabras clave: | 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ño: | 2018 |
| Volumen: | 130 |
| Página de inicio: | 11 |
| Página de fin: | 15 |
| DOI: | http://dx.doi.org/10.1016/j.ipl.2017.09.014 |
| Título revista: | Information Processing Letters |
| Título revista abreviado: | Inf. Process. Lett. |
| ISSN: | 00200190 |
| CODEN: | IFPLA |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v130_n_p11_Lin |
Referencias:
- Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61 (1), pp. 93-101
- Wu, J., Neighborhood-covering and neighborhood-independence in strongly chordal graphs, preprint; Chang, G.J., Farber, M., Tuza, Z., Algorithmic aspects of neighborhood numbers (1993) SIAM J. Discrete Math., 6 (1), pp. 24-29
- Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100 (3), pp. 183-202
- Warnes, X., Structural and Algorithmic Results on Neighborhood-Perfect Graphs and Neighborhood Numbers (2014), Master's thesis Departmento de Matemática, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires Argentina; Gyárfás, A., Kratsch, D., Lehel, J., Maffray, F., Minimal non-neighborhood-perfect graphs (1996) J. Graph Theory, 21 (1), pp. 55-66
- Lehel, J., Neighbourhood-perfect line graphs (1994) Graphs Comb., 10 (2), pp. 353-361
- Hwang, S.-F., Chang, G.J., k-Neighborhood-covering and -independence problems for chordal graphs (1998) SIAM J. Discrete Math., 11 (4), pp. 633-643
- Trevisan, L., Non-approximability results for optimization problems on bounded degree instances (2001) Proceedings of STOC, pp. 453-461
- Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D., Local ratio: a unified framework for approximation algorithms – In memoriam: Shimon Even 1935–2004 (2004) ACM Comput. Surv., 36 (4), pp. 422-463
- Canzar, S., Elbassioni, K.M., Klau, G.W., Mestre, J., On tree-constrained matchings and generalizations (2015) Algorithmica, 71 (1), pp. 98-119
- Corneil, D.G., Perl, Y., Stewart, L.K., A linear recognition algorithm for cographs (1985) SIAM J. Comput., 14 (4), pp. 926-934
- Corneil, D., Lerchs, H., Burlingham, L., Complement reducible graphs (1981) Discrete Appl. Math., 3 (3), pp. 163-174
Citas:
---------- APA ----------
Lin, M.C., Mestre, J. & Vasiliev, S. (2018) . Approximating weighted neighborhood independent sets. Information Processing Letters, 130, 11-15.http://dx.doi.org/10.1016/j.ipl.2017.09.014
---------- CHICAGO ----------
Lin, M.C., Mestre, J., Vasiliev, S. "Approximating weighted neighborhood independent sets" . Information Processing Letters 130 (2018) : 11-15.http://dx.doi.org/10.1016/j.ipl.2017.09.014
---------- MLA ----------
Lin, M.C., Mestre, J., Vasiliev, S. "Approximating weighted neighborhood independent sets" . Information Processing Letters, vol. 130, 2018, pp. 11-15.http://dx.doi.org/10.1016/j.ipl.2017.09.014
---------- VANCOUVER ----------
Lin, M.C., Mestre, J., Vasiliev, S. Approximating weighted neighborhood independent sets. Inf. Process. Lett. 2018;130:11-15.http://dx.doi.org/10.1016/j.ipl.2017.09.014
