INVESTIGADORES
BONOMO Flavia
artículos
Título:
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
Autor/es:
BONOMO, FLAVIA; DURÁN, GUILLERMO; NAPOLI, AMEDEO; VALENCIA-PABON, MARIO
Revista:
INFORMATION PROCESSING LETTERS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2015 vol. 115 p. 600 - 603
ISSN:
0020-0190
Resumen:
In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph and potentially optimal solutions for the minimum sum coloring problem in its complement. We apply this correspondence to polynomially solve the cluster deletion problem in a subclass of $P_4$-sparse graphs that strictly includes $P_4$-reducible graphs.