A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4-sparse graphs | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| 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 | Universidad de Chile | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Université de Lorraine | |
| dc.conicet.organizacion | Universite de Paris 13-Nord | |
| dc.contributor.author | Bonomo, Flavia | |
| dc.contributor.author | Duran, Guillermo Alfredo | |
| dc.contributor.author | Napoli, Amedeo | |
| dc.contributor.author | Valencia Pabon, Mario | |
| dc.date.issued | 2015-08 | |
| dc.description.abstract | In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph G and potentially optimal solutions for the minimum sum coloring problem in G (i.e. the complement graph of G). We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of P4-sparse graphs that strictly includes P4-reducible graphs. | es |
| dc.description.fil | Fil: Bonomo, Flavia. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Duran, Guillermo Alfredo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Cálculo; Argentina. Universidad de Chile; Chile. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Napoli, Amedeo. Université de Lorraine; Francia | |
| dc.description.fil | Fil: Valencia Pabon, Mario. Universite de Paris 13-Nord; Francia | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Bonomo, Flavia; Duran, Guillermo Alfredo; Napoli, Amedeo; Valencia Pabon, Mario; A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4-sparse graphs; Elsevier Science; Information Processing Letters; 115; 6-8; 8-2015; 600-603 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0020-0190 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/18956 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 6-8 | es |
| dc.journal.pagination | 600-603 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Information Processing Letters | es |
| dc.journal.volume | 115 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ipl.2015.02.007 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0020019015000241 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Cliques | es |
| dc.subject | Edge-Deletion | es |
| dc.subject | Cluster Deletion | es |
| dc.subject | Sum Coloring | es |
| dc.subject | Integer Sequences | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | 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 | A one-to-one correspondence between potential solutions of the cluster deletion problem and the minimum sum coloring problem, and its application to P4-sparse graphs | 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.22756.pdf
- Tamaño:
- 233.61 KB
- Formato:
- Adobe Portable Document Format