Biblioteca Digital | FCEN-UBA

Biblioteca Digital ¿Por qué?
Objetivos
Impactos
Estadísticas
Documentos
Presentaciones
Notas
Autores y derechos
¿Por qué depositar?
¿Cómo depositar?
Autorización
Depositar y publicar
Editoriales
Publicar mi tesis Formulario Tesis Posgrado
Formulario Tesis Grado
Normativa
Res. CD 2053/05
Res. CD 2533/09
Res. CD 0272/13
Res. CD 2793/15

Colecciones Tesis Doctorales
Fotografías
Publicaciones
Archivo
Libros
Reportes Técnicos

Tesis > TEMA

Matemática [ 112 tesis ]

Teoría de Grafos [ 3 tesis ]

Bressan, Juan Carlos. "Sistemas axiomáticos para la convexidad" (1976) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Registro Cita

Grippo, Luciano Norberto. "Caracterizaciones estructurales de grafos de intersección" (2011) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

Resumen:
En esta tesis estudiamos caracterizaciones estructurales para grafos arcocirculares, grafos circulo, grafos probe de intervalos, grafos probe de interva 10s unitarios, grafos probe de bloques y grafos probe co-bipartitos. Un grafo es arc0 circular (circulo) si es el grafo de interseccion de una familia de arcos (cuerdas) en una circunferencia. Dada una familia hereditaria de grafos G, un grafo es probe G si sus vertices pueden particionarse en dos conjuntos: un conjunto de vertices probe y un conjunto de vertices nonprobe, de forma tal que el conjunto de vertices nonprobe es un conjunto independiente y es posible obtener un grafo en la clase G agregando aristas entre ellos. Los grafos probe G forman una superclase de la familia G. Por lo tanto, 10s grafos probe de intervalos y 10s grafos probe de intervalos unitarios generalizan la clase de 10s grafos de intervalos y 10s grafos de intervalos unitarios respectivamente. Caracterizamos parcialmente a 10s grafos arco-circulares, grafos circulo, grafos probe de intervalos y probe de interval0 unitario mediante subgrafos prohibidos dentro de ciertas familias hereditarias de grafos. Finalmente, es presentada una caracterizacion de 10s grafos probe co-bipartitos que lleva a un algoritmo de reconocimiento de tiempo polinomial para dicha clase y 10s grafos probe de bloques son caracterizados mediante una lista de subgrafos prohibidos.

Abstract:
In this Thesis we study structural characterizations for six classes of graphs, namely circular-arc graphs, circle graphs, probe interval graphs, probe unit interval graphs, probe co-bipartite graphs, and probe block graphs. A circular-arc graph (circle graph) is the intersection graph of a family of arcs (chords) on a circle. Let G be a hereditary class of graphs. A graph is probe G if its vertices can be partitioned into two sets: a set of probe vertices and a set of nonprobe vertices, so that the set of nonprobe vertices is a stable set and it is possible to obtain a graph belonging to the class G by adding edges with both endpoints in the set of nonprobe vertices. Probe G graphs form a superclass of the class G. Hence, probe interval graphs and probe unit interval graphs are extensions of the classes of interval graphs and unit interval graphs, respectively. We partially characterize circular-arc graphs, circle graphs, probe interval graphs and probe unit interval graphs by forbidden induced subgraphs within certain hereditary families of graphs. Finally, a structural characterization for probe co-bipartite graphs that leads to a polynomial-time recognition algorithm and a complete characterization of probe block graphs by a list of forbidden induced subgraphs are presented.

Severin, Daniel E.. "Estudio poliedral y algoritmo branch-and-cut para el problema de coloreo equitativo en grafos" (2012) Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires

pdf

Resumen Registro Cita

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.

http://digital.bl.fcen.uba.ar

Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34