Tesis > Documento


Ver el documento (formato PDF)   Koch, Ivo Valerio.  "Un enfoque algorítmico sobre algunas variantes del problema de coloreo de grafos y el problema de conjunto independiente máximo"  (2014-08-21)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
En esta Tesis estudiamos variantes del problema de coloreo de grafos para varias familias de grafos, y analizamos el problema del conjunto independiente máximo bajo un enfoque de generación de planos de corte. En el problema del k; i-coloreo, asignamos conjuntos de colores de cardinalidad k a los vértices de un grafo G, de manera que los conjuntos que correspondan a vértices adyacentes en G intersequen en no más de i elementos y la cantidad total de colores usados sea mínima. Esta cantidad mínima recibe el nombre de número k; i-cromático y es denotada por Xik(G). Este parámetro, que generaliza el número cromático X01(G), es tan difícil de trabajar que su valor es desconocido aún para grafos completos. Desarrollamos un algoritmo de orden lineal para el cómputo de Xik para ciclos y generalizamos este resultado a grafos cactus. Adicionalmente, estudiamos la relación entre este problema en grafos completos y un problema abierto clásico de teoría de códigos. Un b-coloreo de un grafo es un coloreo tal que cada clase color admite un vértice adyacente a por lo menos un vértice perteneciente a cada una de las demás clases color. El número b-cromático de un grafo G, denotado como Xb(G), es el máximo número t tal que G admite un b-coloreo con t colores. Describimos un algoritmo polinomial para computar el número b-cromático de la clase de los grafos P4-tidy y estudiamos para esta clase dos propiedades conocidas: la b-continuidad y la b-monotonía. Estudiamos además la versión sobre aristas del b-coloreo y su índice b-cromático asociado. Presentamos cotas para el índice b-cromático del producto directo de grafos y damos resultados generales para varios productos directos de grafos regulares. Introducimos también un modelo sencillo de programación lineal para el b-coloreo de aristas, que utilizamos para calcular resultados exactos para el producto directo de algunas clases de grafos. Finalmente, proponemos un nuevo método de generación de planos de corte para el problema del conjunto independiente máximo. El algoritmo genera desigualdades de rango y otras desigualdades válidas, y utiliza un procedimiento de lifting basado en la resolución del conjunto independiente máximo con pesos sobre un grafo de menor tamaño.

Abstract:
In this Thesis we study variants of the graph coloring problem for several families of graphs, and we address the stable set problem under a new cutting plane generation approach. In the k; i-coloring problem, we assign sets of colors of size k to the vertices of a graph G, so that the sets which belong to adjacent vertices of G intersect in no more than i elements and the total number of colors used is minimum. This minimum number of colors is called k; i-chromatic number and is denoted by Xik(G). This parameter, which generalizes the chromatic number X01 (G), is so difficult to deal with, that its value is unknown even for complete graphs. We develop a linear time algorithm to compute Xik for cycles and generalize the result to cacti. Further, we study the relation between this problem on complete graphs and a classic open problem in coding theory. A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G, denoted by Xb(G), is the maximum number t such that G admits a b-coloring with t colors. We describe a polynomial time algorithm to compute the b-chromatic number for the class of P4-tidy graphs and study this class for two known properties: the b-continuity and the b-monotonicity. We study also the edge version of the b-coloring problem and its associated b-chromatic index for the direct product of graphs and provide general results for many direct products of regular graphs. We introduce a simple linear programming model for the b-edge coloring problem, which we use for computing exact results for the direct product of some special graph classes. Finally, we propose a general procedure for generating cuts for the maximum stable set problem. The algorithm generates both rank and non-rank valid inequalities, and employs a lifting method based on the resolution of a maximum weighted stable set problem on a smaller graph.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Un enfoque algorítmico sobre algunas variantes del problema de coloreo de grafos y el problema de conjunto independiente máximo     =    An algorithmic approach for some variants of the graph coloring problem and the maximum stable set problem
Autor : Koch, Ivo Valerio
Director : Bonomo, Flavia
Director Asistente : Valencia-Pabon, Mario
Consejero : Bonomo, Flavia
Jurados : Linhares-Sales, Claudia  ; Méndez-Díaz, Isabel  ; Sabia, Juan V.R.
Año : 2014-08-21
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Universidad Nacional de General Sarmiento. Instituto de Ciencias
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de Ciencias de la Computación
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5607_Koch
Idioma : Inglés
Area Temática : Computación / Teoría de Grafos
Palabras claves : K, I-COLOREO; GRAFOS CACTUS; B-COLOREO; GRAFOS P4-TIDY; B-COLOREO DE ARISTAS; PRODUCTO DIRECTO DE GRAFOS; CONJUNTO INDEPENDIENTE MAXIMO; PLANOS DE CORTE; ALGORITMOS BRANCH AND CUT; K, I-COLORING; CACTI; B-COLORING; P4-TIDY GRAPHS; B-EDGE-COLORING; DIRECT PRODUCT OF GRAPHS; MAXIMUM STABLE SET; CUTTING PLANE GENERATION; BRANCH AND CUT ALGORITHMS
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     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