Gráficas Dirigidas Acíclicas y sus aplicaciones en computación

Autor: Claudia Paola Medina Santamaria
La Teoría de las Gráficas ha tenido un gran impacto dentro de las Ciencias de la Computación debido a que proporciona una herramienta muy útil para modelar distintos problemas. En esta plática damos un panorama de una clase especial de gráficas, llamadas gráficas dirigidas acíclicas, discutiendo algunas de sus propiedades y mostrando ejemplos de aplicaciones en computación que se sirven de ellas para su desarrollo, por ejemplo algoritmos para resolver el problema SAT y el problema de eliminación de subexpresiones comunes, relevante en la implementación en compiladores. Este trabajo se realiza en el marco del proyecto UNAM PAPIME PE102117.