Approximating weighted neighborhood independent sets | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.conicet.organizacion | University of Sydney | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo | |
| dc.contributor.author | Lin, Min Chih | |
| dc.contributor.author | Mestre, Julian | |
| dc.contributor.author | Vasiliev, Saveliy | |
| dc.date.issued | 2018-02 | |
| dc.description.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 , 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. | es |
| dc.description.fil | Fil: Lin, Min Chih. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina | |
| dc.description.fil | Fil: Mestre, Julian. University of Sydney; Australia | |
| dc.description.fil | Fil: Vasiliev, Saveliy. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Lin, Min Chih; Mestre, Julian; Vasiliev, Saveliy; Approximating weighted neighborhood independent sets; Elsevier Science; Information Processing Letters; 130; 2-2018; 11-15 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0020-0190 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/92377 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 11-15 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Information Processing Letters | es |
| dc.journal.volume | 130 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://linkinghub.elsevier.com/retrieve/pii/S0020019017301709 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2017.09.014 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | APPROXIMATION ALGORITHMS | es |
| dc.subject | GRAPH ALGORITHMS | es |
| dc.subject | WEIGHTED NEIGHBORHOOD INDEPENDENT SET | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Approximating weighted neighborhood independent sets | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.5db8f09c-7e70-4d0a-ab3d-bed5e60e0952_A.pdf
- Tamaño:
- 260.4 KB
- Formato:
- Adobe Portable Document Format