Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
Fecha
2021-03-10
Autores
Título de la revista
ISSN de la revista
Título del volumen
Editor
Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario
Resumen
En teoría de grafos, el problema de encontrar el conjunto independiente máximo (MIS, por sus siglas en inglés), y el problema de encontrar el conjunto de golpe mínimo (MHS), son de vital relevancia en el campo de estudi. En cuanto a la complejidad computacional, ambos son NP difíciles (incluso de aproximación) para grafos en general. En esta tesina, nos centramos en las familias de grafos de rectángulos, cuadrados y de ganchos, que son entradas más simples para esta problemática. Estudiamos, asimismo, algunos problemas combinatorios extremales, y analizamos de qué manera pueden utilizarse para obtener algoritmos de aproximación para MIS y MHS en estas clases de grafos.
Descripción
Palabras clave
Teoría de grafos, Grafos rectángulos, Conjunto de golpe, Matemática aplicada, Brecha de dualidad, Número de Ramsey