Catálogo de publicaciones - tesis
Título de Acceso Abierto
Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
Daniel E. Severin Isabel Méndez-Díaz Graciela L. Nasini
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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.Palabras clave – provistas por el repositorio digital
BRANCH-AND-CUT; COLOREO EQUITATIVO DE GRAFOS; PROGRAMACION LINEAL ENTERA; POLIEDROS; PLANOS DE CORTE; EQUITABLE GRAPH COLORING; INTEGER LINEAR PROGRAMMING; POLYHEDRA; CUTTING PLANE
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2012 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2012
Información sobre licencias CC
