An exact algorithm for the adjacent vertex distinguishing sum edge coloring problem | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.contributor.author | Curcio, Brian Luis | |
| dc.contributor.author | Méndez-Díaz, Isabel | |
| dc.contributor.author | Zabala, Paula Lorena | |
| dc.date.issued | 2025-08 | |
| dc.description.abstract | In this work we define the adjacent vertex distinguishing sum edge coloring problem. This problem consists of finding an assignment of colors to the edges of a graph with the following constraints: every pair of adjacent edges must have a different color, and every pair of adjacent vertices must not have the same set of colors assigned to the edges incident to each. The goal is to minimize the sum of the colors in an edge coloring that satisfies these constraints. This problem is a special case of a large family of problems known as graph labeling, which is a widely used and very popular set of tools to build abstract models for problems that arise in everyday life. Some variants of graph labeling problems have been successfully addressed with mixed-integer linear programming (MIP) techniques based on a polyhedral characterization of the set of feasible solutions. We use this approach to develop a Branch and Cut algorithm to solve the problem. We propose two MIP models that are computationally evaluated to choose the most promising one and continue with a polyhedral study. This analysis aims to characterize valid inequalities that strengthen the formulation in the hope of improving the algorithm’s performance. These inequalities are added on demand as cutting planes using exact and heuristic separation algorithms. Additionally, we considered the use of an initial heuristic and a specific branching strategy. The results show that the algorithm developed allows us to solve instances that were unsolvable using general-purpose solvers. Our polyhedral study and the addition of cutting planes have proved to be crucial factors in solving the most challenging instances. | es |
| dc.description.fil | Fil: Curcio, Brian Luis. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.description.fil | Fil: Méndez-Díaz, Isabel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.description.fil | Fil: Zabala, Paula Lorena. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria. Instituto de Investigación en Ciencias de la Computación. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Instituto de Investigación en Ciencias de la Computación; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Curcio, Brian Luis; Méndez-Díaz, Isabel; Zabala, Paula Lorena; An exact algorithm for the adjacent vertex distinguishing sum edge coloring problem; Elsevier Science; Discrete Applied Mathematics; 371; 8-2025; 80-98 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0166-218X | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/281708 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 80-98 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Discrete Applied Mathematics | es |
| dc.journal.volume | 371 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/abs/pii/S0166218X25001532 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/https://doi.org/10.1016/j.dam.2025.03.029 | |
| dc.rights | info:eu-repo/semantics/restrictedAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | INTEGER PROGRAMMING | es |
| dc.subject | EDGE COLORING | es |
| dc.subject | ADJACENT VERTEX DISTINGUISHING | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | An exact algorithm for the adjacent vertex distinguishing sum edge coloring problem | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.b58ef98c-3886-4455-9ee9-b356d0e66f84_E.pdf
- Tamaño:
- 724.83 KB
- Formato:
- Adobe Portable Document Format