Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | computacion |
| Título: | Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos |
| Título alternativo: | A polyhedral study and a Branch-and-Cut algorithm for the equitable graph coloring problem |
| Autor: | Severin, Daniel Esteban |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Universidad Nacional de Rosario. Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Departamento de Matemática
|
| Publicación en la Web: | 2012-09-14 |
| Fecha de defensa: | 2012 |
| Fecha en portada: | 2012 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación |
| Director: | Méndez-Díaz, Isabel; Nasini, Graciela L. |
| Jurado: | Marenco, Javier; Maculán, Nelson; Cancela Bosi, Héctor |
| Idioma: | Español |
| Palabras clave: | BRANCH-AND-CUT; COLOREO EQUITATIVO DE GRAFOS; PROGRAMACION LINEAL ENTERA; POLIEDROS; PLANOS DE CORTEBRANCH-AND-CUT; EQUITABLE GRAPH COLORING; INTEGER LINEAR PROGRAMMING; POLYHEDRA; CUTTING PLANE |
| Tema: | computación/teoría de grafos
matemática/teoría de grafos
|
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n5080_Severin |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5080_Severin.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n5080_Severin |
| Ubicación: | Dep.COM 005080 |
| 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. Severin, Daniel Esteban. (2012). Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n5080_Severin |
Resumen:
Los problemas de coloreo de grafos constituyen una familia de problemas de una gran relevancia tanto teórica como práctica. Todos ellos son variaciones del problema del coloreo clásico, cuyo estudio se inició en el Siglo XIX. El origen de estas variaciones radica en las restricciones adicionales que imponen las aplicaciones a problemas de la vida real. En esta tesis abordamos en particular el Problema de Coloreo Equitativo en Grafos. Como muchos problemas de Optimización Combinatoria, el Problema de Coloreo Equitativo es un problema NP-difícil. Los algoritmos Branch-and-Cut basados en el estudio poliedral de una formulación del problema como programa lineal entero, son la herramienta más efectiva que se conoce para la resolución exacta de problemas NP-difíciles. En esta tesis se propone un modelo de programación lineal entera para el Problema del Coloreo Equitativo y se estudia el poliedro asociado. Se derivan varias familias de desigualdades validas y se prueba que siempre definen caras de alta dimensión, lo cual es un buen indicador para la utilización de las mismas como planos de corte. Finalmente, se desarrolla e implementa un algoritmo Branch-and-Cut para el Problema de Coloreo Equitativo que resulta altamente competitivo con los algoritmos exactos conocidos.
Abstract:
The graph coloring problems constitute a family of problems of great theoretical and practical relevance. All of them are variations of the classical coloring problem, whose study began in the nineteenth century. The origin of these variations arises from the additional restrictions imposed by applications to real life problems. In particular, this thesis deals with the Equitable Graph Coloring Problem. Like many combinatorial optimization problems, the Equitable Coloring Problem is NP-hard. It is known that Branch-and-Cut algorithms based on the polyhedral study of a formulation of the problem as an integer linear program, are the most effective tool for solving NP-hard problems. This thesis proposes a linear integer programming model for the Equitable Coloring Problem and studies the polytope associated to that model. Several families of valid inequalities that define faces of high dimension are derived in order to use them later as cutting planes. Finally, a Branch-and-Cut algorithm for the Equitable Coloring Problem that is highly competitive against known exact algorithms is developed.
Citación:
---------- APA ----------
Severin, Daniel Esteban. (2012). Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n5080_Severin
---------- CHICAGO ----------
Severin, Daniel Esteban. "Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2012.https://hdl.handle.net/20.500.12110/tesis_n5080_Severin
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n5080_Severin.pdf
