ICC 25427
INSTITUTO DE INVESTIGACION EN CIENCIAS DE LA COMPUTACION
Unidad Ejecutora - UE
congresos y reuniones científicas
Título:
A polyhedral approach to the adjacent vertex distinguishable proper edge coloring problem
Autor/es:
MÉNDEZ-DÍAZ, ISABEL; CURCIO, BRIAN; ZABALA, PAULA
Lugar:
Santiago de Chile
Reunión:
Conferencia; CLAIO 2016; 2016
Institución organizadora:
ALIO
Resumen:
The adjacent vertex distinguishable proper edge coloring problem is the problem of finding the minimum number of colors required for a proper edge coloring such that every pair of adjacent vertices is distinguishable.In this paper we propose an integer linear programming approach to solve the problem. We study the underlying polyhedron, develop a Branch and Cut algorithm and present computational results that show a very good performance of the algorithm on random graphs.
