A DSATUR-based algorithm for the Equitable Coloring Problem

dc.creatorMéndez-Díaz, Isabel
dc.creatorNasini, Graciela Leonor
dc.creatorSeverin, Daniel Esteban
dc.date.accessioned2018-03-08T21:57:37Z
dc.date.accessioned2018-11-06T11:30:35Z
dc.date.available2018-03-08T21:57:37Z
dc.date.available2018-11-06T11:30:35Z
dc.date.created2018-03-08T21:57:37Z
dc.date.issued2015-02
dc.identifierMéndez-Díaz, Isabel; Nasini, Graciela Leonor; Severin, Daniel Esteban; A DSATUR-based algorithm for the Equitable Coloring Problem; Pergamon-Elsevier Science Ltd; Computers & Operations Research; 57; 2-2015; 41-50
dc.identifier0305-0548
dc.identifierhttp://hdl.handle.net/11336/38356
dc.identifierCONICET Digital
dc.identifierCONICET
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1853744
dc.description.abstractThis paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.
dc.languageeng
dc.publisherPergamon-Elsevier Science Ltd
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0305054814003189
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.cor.2014.11.014
dc.relationinfo:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1306.1758
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/openAccess
dc.subjectDSATUR
dc.subjectEQUITABLE COLORING
dc.subjectEXACT ALGORITHM
dc.titleA DSATUR-based algorithm for the Equitable Coloring Problem
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución