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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , |
| Formato: | Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier B.V.
2018
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 05210caa a22006737a 4500 | ||
|---|---|---|---|
| 001 | PAPER-17166 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518204819.0 | ||
| 008 | 190410s2018 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-85030465939 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 030 | |a IFPLA | ||
| 100 | 1 | |a Lin, M.C. | |
| 245 | 1 | 0 | |a Approximating weighted neighborhood independent sets |
| 260 | |b Elsevier B.V. |c 2018 | ||
| 270 | 1 | 0 | |m Vasiliev, S.; CONICET, Instituto de Cálculo, FCEyN, Universidad de Buenos AiresArgentina; email: svassiliev@dc.uba.ar |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a Lehel, J., Tuza, Z., Neighborhood perfect graphs (1986) Discrete Math., 61 (1), pp. 93-101 | ||
| 504 | |a 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 | ||
| 504 | |a Guruswami, V., Rangan, C.P., Algorithmic aspects of clique-transversal and clique-independent sets (2000) Discrete Appl. Math., 100 (3), pp. 183-202 | ||
| 504 | |a 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 | ||
| 504 | |a Lehel, J., Neighbourhood-perfect line graphs (1994) Graphs Comb., 10 (2), pp. 353-361 | ||
| 504 | |a 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 | ||
| 504 | |a Trevisan, L., Non-approximability results for optimization problems on bounded degree instances (2001) Proceedings of STOC, pp. 453-461 | ||
| 504 | |a 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 | ||
| 504 | |a Canzar, S., Elbassioni, K.M., Klau, G.W., Mestre, J., On tree-constrained matchings and generalizations (2015) Algorithmica, 71 (1), pp. 98-119 | ||
| 504 | |a Corneil, D.G., Perl, Y., Stewart, L.K., A linear recognition algorithm for cographs (1985) SIAM J. Comput., 14 (4), pp. 926-934 | ||
| 504 | |a Corneil, D., Lerchs, H., Burlingham, L., Complement reducible graphs (1981) Discrete Appl. Math., 3 (3), pp. 163-174 | ||
| 520 | 3 | |a 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 |l eng | |
| 536 | |a Detalles de la financiación: 2013-2205 | ||
| 536 | |a Detalles de la financiación: Secretaría de Ciencia y Técnica, Universidad de Buenos Aires, 20020120100058 | ||
| 536 | |a Detalles de la financiación: We appreciate the comments of the reviewers, which significantly helped us improving the presentation and clarity of this work. This work was partially supported by UBACyT Grant 20020120100058 , and PICT ANPCyT Grant 2013-2205 . | ||
| 593 | |a CONICET, Instituto de Cálculo, FCEyN, Universidad de Buenos Aires, Argentina | ||
| 593 | |a The University of Sydney, Australia | ||
| 690 | 1 | 0 | |a APPROXIMATION ALGORITHMS |
| 690 | 1 | 0 | |a GRAPH ALGORITHMS |
| 690 | 1 | 0 | |a WEIGHTED NEIGHBORHOOD INDEPENDENT SET |
| 690 | 1 | 0 | |a APPROXIMATION ALGORITHMS |
| 690 | 1 | 0 | |a COMPUTATIONAL COMPLEXITY |
| 690 | 1 | 0 | |a PROBLEM SOLVING |
| 690 | 1 | 0 | |a APPROXIMATION RATIOS |
| 690 | 1 | 0 | |a DIAMOND-FREE GRAPHS |
| 690 | 1 | 0 | |a GENERAL GRAPH |
| 690 | 1 | 0 | |a GRAPH ALGORITHMS |
| 690 | 1 | 0 | |a INDEPENDENT SET |
| 690 | 1 | 0 | |a MAXIMUM DEGREE |
| 690 | 1 | 0 | |a POLYNOMIALLY SOLVABLE |
| 690 | 1 | 0 | |a REGULAR GRAPHS |
| 690 | 1 | 0 | |a GRAPH THEORY |
| 700 | 1 | |a Mestre, J. | |
| 700 | 1 | |a Vasiliev, S. | |
| 773 | 0 | |d Elsevier B.V., 2018 |g v. 130 |h pp. 11-15 |p Inf. Process. Lett. |x 00200190 |w (AR-BaUEN)CENRE-1599 |t Information Processing Letters | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-85030465939&doi=10.1016%2fj.ipl.2017.09.014&partnerID=40&md5=b404b29a46bed8b560ca4e7ffe1a1067 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1016/j.ipl.2017.09.014 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_00200190_v130_n_p11_Lin |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_00200190_v130_n_p11_Lin |y Registro en la Biblioteca Digital |
| 961 | |a paper_00200190_v130_n_p11_Lin |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 999 | |c 78119 | ||