Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
Cargando...
Fecha
Authors
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
Citación
Aprobación
Revisión
Complementado por
Referenciado por
Licencia Creative Commons
Excepto donde se indique lo contrario, la licencia de este ítem se describe como Reconocimiento - Compartir igual (by-sa): Se permite el uso comercial de LA OBRA y de las posibles obras derivadas, la distribución de las cuales se debe hacer con una licencia igual a la que regula LA OBRA original.