Registro:
| Documento: | Tesis de Grado |
| Título: | Problema de coloreo propio de aristas con distinguibilidad |
| Título alternativo: | The problem of proper edge coloring with distinguishability |
| Autor: | Rabinowicz, Julia |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Fecha de defensa: | 2025-12-19 |
| Fecha en portada: | 2025 |
| Grado Obtenido: | Grado |
| Título Obtenido: | Licenciado en Ciencias de la Computación |
| Departamento Docente: | Departamento de Computación |
| Director: | Méndez Díaz, Isabel |
| Director Asistente: | Zabala, Paula Lorena |
| Jurado: | Curcio, Brian Luis; Negrotto, Daniel |
| Idioma: | Español |
| Palabras clave: | COLOREO DE ARISTAS; DISTINGUIBILIDAD; PROGRAMACION LINEAL ENTERA; BRANCH-AND-CUT; HEURISTICA INICIAL; DESIGUALDADES VALIDAS; HEURISTICA PRIMAL; BUSQUEDA LOCAL; BUSQUEDA TABUEDGE COLORING; DISTINGUISHABILITY; INTEGER LINEAR PROGRAMMING; BRANCH-AND-CUT; INITIAL HEURISTIC; VALID INEQUALITIES; PRIMAL HEURISTIC; LOCAL SEARCH; TABU SEARCH |
| Formato: | PDF |
| Handle: |
https://hdl.handle.net/20.500.12110/seminario_nCOM000877_Rabinowicz |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000877_Rabinowicz.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/seminario/document/seminario_nCOM000877_Rabinowicz |
| Ubicación: | COM 000877 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Rabinowicz, Julia. (2025). Problema de coloreo propio de aristas con distinguibilidad. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000877_Rabinowicz |
Resumen:
En esta tesis se trabaja con el problema de coloreo propio de aristas con distinguibilidad por suma. Se propone una solución a dicho problema utilizando un enfoque de programación lineal entera. El objetivo del presente estudio es desarrollar un algoritmo Branch and Cut que resuelva el problema de la manera más eficiente posible. Bajo esta premisa, se exponen dos formulaciones de programación lineal entera diferentes que son comparadas para elegir la de mejor performance. Una vez determinado el mejor modelo, se exponen una heurística inicial, planos de corte basados en desigualdades válidas encontradas para dicho modelo y una heurística primal con el fin de potenciar al algoritmo. Asimismo, se realiza un análisis comparativo entre el método exacto propuesto y dos heurísticas, una búsqueda local y otra basada en un esquema de búsqueda tabú. Finalmente, se expone el mismo estudio para la implementación de un algoritmo Branch and Cut eficiente pero enfocado en una versión relajada del problema, junto con un análisis comparativo de los resultados de la versión relajada y los de la versión original.
Abstract:
In this thesis we work with the problem of proper edge coloring with sum distinguishability. A solution to this problem is proposed using an integer linear programming approach. The goal of the present study is to develop a Branch and Cut algorithm that solves the problem in the most efficient way possible. Under this premise, two different integer linear programming formulations are presented and compared in order to choose the one with the best performance. Once the best model is determined, an initial heuristic, cutting planes based on valid inequalities found for said model and a primal heuristic are put forward to enhance the algorithm. A comparative analysis is also performed between the proposed exact method and two heuristics, one based on local search and the other on a tabu search scheme. Finally, the same analysis is presented for the implementation of an efficient Branch and Cut algorithm but focused on a relaxed version of the problem, along with a comparative analysis of the results of the relaxed version and those of the original version.
Citación:
---------- APA ----------
Rabinowicz, Julia. (2025). Problema de coloreo propio de aristas con distinguibilidad. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000877_Rabinowicz
---------- CHICAGO ----------
Rabinowicz, Julia. "Problema de coloreo propio de aristas con distinguibilidad". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2025.https://hdl.handle.net/20.500.12110/seminario_nCOM000877_Rabinowicz
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000877_Rabinowicz.pdf
Distrubución geográfica
