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

dc.creatorBonomo, Flavia
dc.creatorDurán Maggiolo, Guillermo
dc.creatorNapoli, Amedeo
dc.creatorValencia Pabon, Mario
dc.date.accessioned2015-08-17T20:27:33Z
dc.date.available2015-08-17T20:27:33Z
dc.date.created2015-08-17T20:27:33Z
dc.date.issued2015
dc.identifierInformation Processing Letters 115 (2015) 600–603
dc.identifierDOI: http://dx.doi.org/10.1016/j.ipl.2015.02.007
dc.identifierhttps://repositorio.uchile.cl/handle/2250/132803
dc.description.abstractIn 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.
dc.languageen
dc.publisherElsevier
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile
dc.subjectCluster deletion
dc.subjectSum coloring
dc.subjectP4-sparse
dc.subjectGraph algorithms
dc.titleA one-to-one correspondence between potential solutions ofthe cluster deletion problem and the minimum sum coloring problem, and its application to P4-sparse graphs
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución