Reducción de grafos sin pérdida de información

Resumen

Los algoritmos relacionados con la teoría de grafos han sido ampliamente estudiados. Varios estudios se enfocan en la disminución de la complejidad temporal de estos algoritmos. Las técnicas utilizadas en este sentido, generalmente se basan en reducir un grafo o el espacio de búsqueda de solución, eliminando información redundante para el problema específico que se desea resolver. El proceso de reducción de un grafo consiste en obtener grafos más pequeños (con menos vértices) que tengan las características principales o relevantes del grafo original. En el caso de la búsqueda de caminos óptimos, los algoritmos que hacen uso de la reducción de grafos o del espacio de búsqueda de solución, no garantizan la obtención del óptimo en todos los casos. Lo mismo ocurre en otros tipos de problemas tales como la reducción de grafos en redes de workflow, de computadoras, etc. En este trabajo se propone un algoritmo de reducción de grafos sin pérdida de información. La propuesta tiene una forma flexible de especificar la manera en que se quiere reducir el grafo; por consiguiente, puede ser utilizada en la solución de varios tipos de problemas.