Examinando por Autor "Capretto, Margarita"

Mostrando 1 - 1 de 1
  • Miniatura
    ÍtemAcceso Abierto
    Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
    (Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario, 2021-03-10) Capretto, Margarita; Chalermsook, Parinya; Torres , Pablo
    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.