Brecha de dualidad y límites de tipo Ramsey para familias de grafos de intersección de rectángulo
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 ap...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | |
| Formato: | bachelorThesis Tésis de Grado |
| Lenguaje: | Español |
| Publicado: |
Facultad de Ciencias Exactas, Ingeniería y Agrimensura. Universidad Nacional de Rosario
2022
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/2133/23731 http://hdl.handle.net/2133/23731 |
| Aporte de: |
| Sumario: | 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. |
|---|