Catálogo de publicaciones - tesis
Título de Acceso Abierto
Un enfoque algorítmico sobre algunas variantes del problema de coloreo de grafos y el problema de conjunto independiente máximo
Ivo Valerio Koch Flavia Bonomo
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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.Palabras clave – provistas por el repositorio digital
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
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2014 | 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
2014-08-21
Información sobre licencias CC
