Chalermsook, Parinya2022-05-242022-05-242021-03-10http://hdl.handle.net/2133/23731En 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.application/pdfspaopenAccessTeoría de grafosGrafos rectángulosConjunto de golpeMatemática aplicadaBrecha de dualidadNúmero de RamseybachelorThesisCapretto, MargaritaReconocimiento - 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.