Mostrar el registro sencillo del ítem

dc.contributor.author
Bonomo, Flavia  
dc.contributor.author
Duran, Guillermo Alfredo  
dc.contributor.author
Napoli, Amedeo  
dc.contributor.author
Valencia Pabon, Mario  
dc.date.available
2017-06-26T21:40:06Z  
dc.date.issued
2015-08  
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  
dc.identifier.issn
0020-0190  
dc.identifier.uri
http://hdl.handle.net/11336/18956  
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.  
dc.format
application/pdf  
dc.language.iso
eng  
dc.publisher
Elsevier Science  
dc.rights
info:eu-repo/semantics/openAccess  
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/  
dc.subject
Cliques  
dc.subject
Edge-Deletion  
dc.subject
Cluster Deletion  
dc.subject
Sum Coloring  
dc.subject
Integer Sequences  
dc.subject.classification
Matemática Aplicada  
dc.subject.classification
Matemáticas  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
dc.subject.classification
Ciencias de la Computación  
dc.subject.classification
Ciencias de la Computación e Información  
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS  
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  
dc.type
info:eu-repo/semantics/article  
dc.type
info:ar-repo/semantics/artículo  
dc.type
info:eu-repo/semantics/publishedVersion  
dc.date.updated
2017-06-26T14:06:54Z  
dc.journal.volume
115  
dc.journal.number
6-8  
dc.journal.pagination
600-603  
dc.journal.pais
Países Bajos  
dc.journal.ciudad
Amsterdam  
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.journal.title
Information Processing Letters  
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  

Archivos asociados
Thumbnail
 
Tamaño: 233.6Kb
Formato: PDF
.