Artículo de revista
A one-to-one correspondence between potential solutions ofthe cluster deletion problem and the minimum sum coloring problem, and its application to P4-sparse graphs
Fecha
2015Registro en:
Information Processing Letters 115 (2015) 600–603
Autor
Bonomo, Flavia
Durán Maggiolo, Guillermo
Napoli, Amedeo
Valencia Pabon, Mario
Institución
Resumen
In this note we show a one-to-one correspondence between potentially optimal solutions to the cluster deletion problem in a graph Gand 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.