Artículo

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

Bonomo, FlaviaIcon ; Duran, Guillermo AlfredoIcon ; Napoli, Amedeo; Valencia Pabon, Mario
Fecha de publicación: 08/2015
Editorial: Elsevier Science
Revista: Information Processing Letters
ISSN: 0020-0190
Idioma: Inglés
Tipo de recurso: Artículo publicado
Clasificación temática:

Resumen

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.
Palabras clave: Cliques , Edge-Deletion , Cluster Deletion , Sum Coloring , Integer Sequences
 
Archivos asociados
Thumbnail
 
Tamaño: 233.6Kb
Formato: PDF
.
Licencia
info:eu-repo/semantics/openAccess Excepto donde se diga explícitamente, este item se publica bajo la siguiente descripción: Atribución-NoComercial-SinDerivadas 2.5 Argentina (CC BY-NC-ND 2.5 AR)
Identificadores
URI: http://hdl.handle.net/11336/18956
DOI: http://dx.doi.org/10.1016/j.ipl.2015.02.007
URL: http://www.sciencedirect.com/science/article/pii/S0020019015000241
Colecciones
Articulos(IMAS)
Articulos de INSTITUTO DE INVESTIGACIONES MATEMATICAS "LUIS A. SANTALO"
Citación
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
Compartir
Altmétricas