The minimum chromatic violation problem : a polyhedral approach
Revista con referato
| Autores principales: | , , , , , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
Elsevier Science BV
2025
|
| Materias: | |
| Acceso en línea: | http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2036 |
| Aporte de: |
| id |
I71-R177-UNGS-2036 |
|---|---|
| record_format |
dspace |
| institution |
Universidad Nacional de General Sarmiento |
| institution_str |
I-71 |
| repository_str |
R-177 |
| collection |
Repositorio Institucional Digital de Acceso Abierto (UNGS) |
| language |
Inglés |
| orig_language_str_mv |
eng |
| topic |
Chromatic violation Graph coloring K-partition Polyhedral study Matemáticas |
| spellingShingle |
Chromatic violation Graph coloring K-partition Polyhedral study Matemáticas Braga, Mónica Andrea Delle Donne, Diego Escalante, Mariana Silvina Marenco, Javier Ugarte, María Elisa Varaldo, María del Carmen The minimum chromatic violation problem : a polyhedral approach |
| topic_facet |
Chromatic violation Graph coloring K-partition Polyhedral study Matemáticas |
| description |
Revista con referato |
| format |
Artículo Artículo publishedVersion |
| author |
Braga, Mónica Andrea Delle Donne, Diego Escalante, Mariana Silvina Marenco, Javier Ugarte, María Elisa Varaldo, María del Carmen |
| author_facet |
Braga, Mónica Andrea Delle Donne, Diego Escalante, Mariana Silvina Marenco, Javier Ugarte, María Elisa Varaldo, María del Carmen |
| author_sort |
Braga, Mónica Andrea |
| title |
The minimum chromatic violation problem : a polyhedral approach |
| title_short |
The minimum chromatic violation problem : a polyhedral approach |
| title_full |
The minimum chromatic violation problem : a polyhedral approach |
| title_fullStr |
The minimum chromatic violation problem : a polyhedral approach |
| title_full_unstemmed |
The minimum chromatic violation problem : a polyhedral approach |
| title_sort |
minimum chromatic violation problem : a polyhedral approach |
| publisher |
Elsevier Science BV |
| publishDate |
2025 |
| url |
http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2036 |
| work_keys_str_mv |
AT bragamonicaandrea theminimumchromaticviolationproblemapolyhedralapproach AT delledonnediego theminimumchromaticviolationproblemapolyhedralapproach AT escalantemarianasilvina theminimumchromaticviolationproblemapolyhedralapproach AT marencojavier theminimumchromaticviolationproblemapolyhedralapproach AT ugartemariaelisa theminimumchromaticviolationproblemapolyhedralapproach AT varaldomariadelcarmen theminimumchromaticviolationproblemapolyhedralapproach AT bragamonicaandrea minimumchromaticviolationproblemapolyhedralapproach AT delledonnediego minimumchromaticviolationproblemapolyhedralapproach AT escalantemarianasilvina minimumchromaticviolationproblemapolyhedralapproach AT marencojavier minimumchromaticviolationproblemapolyhedralapproach AT ugartemariaelisa minimumchromaticviolationproblemapolyhedralapproach AT varaldomariadelcarmen minimumchromaticviolationproblemapolyhedralapproach |
| _version_ |
1824528720694607872 |
| spelling |
I71-R177-UNGS-20362025-02-05T15:23:26Z The minimum chromatic violation problem : a polyhedral approach Braga, Mónica Andrea Delle Donne, Diego Escalante, Mariana Silvina Marenco, Javier Ugarte, María Elisa Varaldo, María del Carmen Chromatic violation Graph coloring K-partition Polyhedral study Matemáticas Revista con referato Fil: Braga, Mónica. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Marenco, Javier. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Delle Donne, Diego. Universite de Paris 13-Nord; Francia. Fil: Escalante, Mariana Silvina. Universidad Nacional de Rosario; Argentina. Fil: Escalante, Mariana Silvina. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Fil: Ugarte, María Elisa. Universidad Nacional de Rosario; Argentina. Fil: Varaldo, María del Carmen. Universidad Nacional de Rosario; Argentina. 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. En este artículo definimos una generalización del problema clásico de coloración de vértices de un gráfico, donde algunos pares de vértices adyacentes pueden asignarse al mismo color. Llamamos débil a una arista que conecta dos de esos vértices. Buscamos una coloración del gráfico minimizando el número de aristas débiles teniendo sus puntos finales asignados al mismo color. Este problema se denomina problema de violación cromática mínima (MCVP). Presentamos una formulación de programación entera para este problema y proporcionamos un estudio poliédrico inicial del politopo que surge de esta formulación. Damos caracterizaciones parciales de desigualdades que inducen facetas y mostramos cómo se relacionan las facetas de diferentes instancias de MCVP. Luego introducimos procedimientos generales de elevación que generan (a veces inducen facetas) desigualdades válidas a partir de desigualdades genéricas válidas. Mostramos varias familias inductoras de facetas que surgen de estos procedimientos y presentamos una familia de desigualdades inductoras de facetas que no se obtiene de los procedimientos de elevación anteriores, asociadas con ciertas subestructuras en el gráfico dado. Finalmente, analizamos el caso extremo de todas las aristas débiles y su relación con el conocido problema de la partición k. Neste artigo definimos uma generalização do problema clássico de coloração de vértices de um grafo, onde alguns pares de vértices adjacentes podem ser atribuídos à mesma cor. Chamamos de fraca uma aresta que conecta dois desses vértices. Procuramos uma coloração do gráfico que minimize o número de arestas fracas tendo seus extremos atribuídos à mesma cor. Este problema é chamado de problema de violação cromática mínima (MCVP). Apresentamos uma formulação de programação inteira para este problema e fornecemos um estudo poliédrico inicial do politopo resultante desta formulação. Damos caracterizações parciais de desigualdades indutoras de facetas e mostramos como as facetas de diferentes instâncias de MCVP estão relacionadas. Em seguida, introduzimos procedimentos gerais de levantamento que geram (às vezes indutores de facetas) desigualdades válidas a partir de desigualdades válidas genéricas. Exibimos várias famílias indutoras de facetas decorrentes desses procedimentos e apresentamos uma família de desigualdades indutoras de facetas que não é obtida nos procedimentos de levantamento anteriores, associadas a certas subestruturas no gráfico fornecido. Finalmente, analisamos o caso extremo de todas as arestas fracas e sua relação com o conhecido problema da k-partição. 2025-02-05T15:23:26Z 2025-02-05T15:23:26Z 2020 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Braga, M., Delle Donne, D., Escalante, M., Marenco, J., Ugarte, M. E. y Varaldo, M. (2020). The minimum chromatic violation problem: a polyhedral approach. Discrete Applied Mathematics, 281, 69-80. 0166-218X http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2036 eng https://doi.org/10.1016/j.dam.2019.05.010 info:eu-repo/semantics/restrictedAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Science BV Discrete Applied Mathematics. Jul. 2020; 281: 69-80 https://www.sciencedirect.com/journal/discrete-applied-mathematics/vol/281/suppl/C |