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
2015, Information Processing Letters 115 (6-8), 600-603, 2015Citas: 16
Agregar PDF Importar citas Importar citas SCRAPME Plots Conexiones
Autor(es)
Flavia Bonomo and Guillermo Duran and Amedeo Napoli and Mario Valencia-Pabon
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¯(ie the complement graph of G). 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.