Mostrar el registro sencillo del ítem
dc.contributor.author
Braga, M.
dc.contributor.author
Delle Donne, D.
dc.contributor.author
Escalante, Mariana Silvina
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Marenco, J.
dc.contributor.author
Ugarte, María Elisa
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Varaldo, María del Carmen
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2022-09-22T11:56:54Z
dc.date.issued
2020-07
dc.identifier.citation
Braga, M.; Delle Donne, D.; Escalante, Mariana Silvina; Marenco, J.; Ugarte, María Elisa; et al.; The minimum chromatic violation problem: A polyhedral approach; Elsevier Science; Discrete Applied Mathematics; 281; 7-2020; 69-80
dc.identifier.issn
0166-218X
dc.identifier.uri
http://hdl.handle.net/11336/169911
dc.description.abstract
In this paper we define a generalization of the classical vertex coloring problem of a graph, where some pairs of adjacent vertices can be assigned to the same color. We call weak an edge connecting two such vertices. We look for a coloring of the graph minimizing the number of weak edges having its endpoints assigned to the same color. This problem is called the minimum chromatic violation problem (MCVP). We present an integer programming formulation for this problem and provide an initial polyhedral study of the polytope arising from this formulation. We give partial characterizations of facet-inducing inequalities and we show how facets from different instances of MCVP are related. We then introduce general lifting procedures which generate (sometimes facet-inducing) valid inequalities from generic valid inequalities. We exhibit several facet-inducing families arising from these procedures and we present a family of facet-inducing inequalities which is not obtained from the prior lifting procedures, associated with certain substructures in the given graph. Finally, we analyze the extreme case of all weak edges and its relationship with the well-known k-partition problem.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/restrictedAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-sa/2.5/ar/
dc.subject
CHROMATIC VIOLATION
dc.subject
GRAPH COLORING
dc.subject
K-PARTITION
dc.subject
POLYHEDRAL STUDY
dc.subject.classification
Otras Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
The minimum chromatic violation problem: A polyhedral approach
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2022-09-19T15:07:37Z
dc.journal.volume
281
dc.journal.pagination
69-80
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Braga, M.. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Delle Donne, D.. Universite de Paris 13-Nord; Francia. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Escalante, Mariana Silvina. Universidad Nacional de Rosario; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina
dc.description.fil
Fil: Marenco, J.. Universidad Nacional de General Sarmiento; Argentina
dc.description.fil
Fil: Ugarte, María Elisa. Universidad Nacional de Rosario; Argentina
dc.description.fil
Fil: Varaldo, María del Carmen. Universidad Nacional de Rosario; Argentina
dc.journal.title
Discrete Applied Mathematics
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.dam.2019.05.010
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0166218X19302677
Archivos asociados