Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos

A polyhedral study and a Branch-and-Cut algorithm for the equitable graph coloring problem

dc.contributorMéndez-Díaz, Isabel
dc.contributorNasini, Graciela L.
dc.creatorSeverin, Daniel E.
dc.date2012
dc.date.accessioned2017-01-24T19:46:23Z
dc.date.available2017-01-24T19:46:23Z
dc.identifierhttp://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5080_Severin
dc.identifierhttp://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=HASH7259b8af4ed58e22dd87a6
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/75149
dc.descriptionLos 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.
dc.formattext; pdf
dc.languageEspañol
dc.publisherFacultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
dc.subjectMatemática / Teoría de Grafos
dc.subjectComputación / Teoría de Grafos
dc.subjectBRANCH-AND-CUT
dc.subjectCOLOREO EQUITATIVO DE GRAFOS
dc.subjectPROGRAMACION LINEAL ENTERA
dc.subjectPOLIEDROS
dc.subjectPLANOS DE CORTE
dc.titleEstudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos
dc.titleA polyhedral study and a Branch-and-Cut algorithm for the equitable graph coloring problem
dc.typeTesis


Este ítem pertenece a la siguiente institución