Facets based on cycles and cliques for the acyclic coloring polytope
Revista con referato
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artículo publishedVersion |
| Lenguaje: | Inglés |
| Publicado: |
EDP Sciences
2025
|
| Materias: | |
| Acceso en línea: | http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2035 |
| Aporte de: |
| id |
I71-R177-UNGS-2035 |
|---|---|
| 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 |
Acyclic coloring Polyhedral combinatorics Combinatorial optimization Coloração acíclica Combinatória poliédrica Otimização combinatória Coloración acíclica Combinatoria poliédrica Optimización combinatoria Matemáticas |
| spellingShingle |
Acyclic coloring Polyhedral combinatorics Combinatorial optimization Coloração acíclica Combinatória poliédrica Otimização combinatória Coloración acíclica Combinatoria poliédrica Optimización combinatoria Matemáticas Braga, Mónica Andrea Marenco, Javier Facets based on cycles and cliques for the acyclic coloring polytope |
| topic_facet |
Acyclic coloring Polyhedral combinatorics Combinatorial optimization Coloração acíclica Combinatória poliédrica Otimização combinatória Coloración acíclica Combinatoria poliédrica Optimización combinatoria Matemáticas |
| description |
Revista con referato |
| format |
Artículo Artículo publishedVersion |
| author |
Braga, Mónica Andrea Marenco, Javier |
| author_facet |
Braga, Mónica Andrea Marenco, Javier |
| author_sort |
Braga, Mónica Andrea |
| title |
Facets based on cycles and cliques for the acyclic coloring polytope |
| title_short |
Facets based on cycles and cliques for the acyclic coloring polytope |
| title_full |
Facets based on cycles and cliques for the acyclic coloring polytope |
| title_fullStr |
Facets based on cycles and cliques for the acyclic coloring polytope |
| title_full_unstemmed |
Facets based on cycles and cliques for the acyclic coloring polytope |
| title_sort |
facets based on cycles and cliques for the acyclic coloring polytope |
| publisher |
EDP Sciences |
| publishDate |
2025 |
| url |
http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2035 |
| work_keys_str_mv |
AT bragamonicaandrea facetsbasedoncyclesandcliquesfortheacycliccoloringpolytope AT marencojavier facetsbasedoncyclesandcliquesfortheacycliccoloringpolytope |
| _version_ |
1824528686632665088 |
| spelling |
I71-R177-UNGS-20352025-02-05T15:23:26Z Facets based on cycles and cliques for the acyclic coloring polytope Braga, Mónica Andrea Marenco, Javier Acyclic coloring Polyhedral combinatorics Combinatorial optimization Coloração acíclica Combinatória poliédrica Otimização combinatória Coloración acíclica Combinatoria poliédrica Optimización combinatoria 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. A coloring of a graph is an assignment of colors to its vertices such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring is a coloring such that no cycle receives exactly two colors, and the acyclic chromatic number ?A(G) of a graph G is the minimum number of colors in any such coloring of G. Given a graph G and an integer k, determining whether ?A(G) ? k or not is NP-complete even for k = 3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In a previous work we presented facet-inducing families of valid inequalities based on induced even cycles for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we continue with this study by introducing new families of facet-inducing inequalities based on combinations of even cycles and cliques. La coloración de un gráfico es una asignación de colores a sus vértices de modo que dos vértices cualesquiera reciban colores distintos siempre que sean adyacentes. Una coloración acíclica es una coloración tal que ningún ciclo recibe exactamente dos colores, y el número cromático acíclico ?A(G) de un gráfico G es el número mínimo de colores en cualquier coloración de G. Dado un gráfico G y un entero k, determinar si ?A(G) ? k o no es NP-completo incluso para k = 3. El problema de la coloración acíclica surge en el contexto de cálculos eficientes de matrices de Hesse dispersas y simétricas mediante sustitución métodos. En un trabajo anterior presentamos familias de desigualdades válidas inductoras de facetas basadas en ciclos pares inducidos para el politopo asociado a una formulación de programación entera del problema de coloración acíclica. En este trabajo continuamos con este estudio introduciendo nuevas familias de desigualdades inductoras de facetas basadas en combinaciones de ciclos pares y camarillas. A coloração de um grafo é uma atribuição de cores aos seus vértices de forma que quaisquer dois vértices recebam cores distintas sempre que forem adjacentes. Uma coloração acíclica é uma coloração tal que nenhum ciclo recebe exatamente duas cores, e o número cromático acíclico ?A(G) de um grafo G é o número mínimo de cores em qualquer coloração de G. Dado um grafo G e um inteiro k, determinar se ?A(G) ? k ou não é NP-completo mesmo para k = 3. O problema de coloração acíclica surge no contexto de cálculos eficientes de matrizes Hessianas esparsas e simétricas por meio de métodos de substituição. Em um trabalho anterior apresentamos famílias indutoras de facetas de desigualdades válidas baseadas em ciclos pares induzidos para o politopo associadas a uma formulação de programação inteira do problema de coloração acíclica. Neste trabalho continuamos com este estudo introduzindo novas famílias de desigualdades indutoras de facetas baseadas em combinações de ciclos pares e cliques. 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., y Marenco, J. (2020). Facets based on cycles and cliques for the acyclic coloring polytope. RAIRO Operations Reserach, 56(6), 1863-1874. 0399-0559 http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2035 eng https://doi.org/10.1051/ro/2019098 info:eu-repo/semantics/restrictedAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf EDP Sciences RAIRO Operations Reserach. Nov.-Dic. 2020; 56(6): 1863-1874 https://www.rairo-ro.org/articles/ro/abs/2020/06/contents/contents.html |