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.Descargas
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
La revista Anales de la Academia de Ciencias de Cuba protege los derechos de autor, y opera con una Licencia Creative Commons 4.0 (Licencia Creative Commons Reconocimiento-NoComerciall 4.0). Al publicar en ella los autores permiten copiar, reproducir, distribuir, comunicar públicamente su obra y generar obras derivadas, siempre y cuando se cite y reconozca al autor original. No permiten, sin embargo, utilizar la obra original con fines comerciales ni lucrativos.
Los autores autorizan la publicación de sus escritos conservando los derechos de autoría, y cediendo y transfiriendo a la revista todos los derechos protegidos por las leyes de propiedad intelectual que rigen en Cuba, que implican la edición para difundir la obra.
Los autores podrán establecer acuerdos adicionales para la distribución no exclusiva de la versión de la obra publicada en la revista (por ejemplo, situarla en un repositorio institucional o publicarla en un libro), con el reconocimiento de haber sido publicada primero en esta revista.
Para conocer más, véase https://creativecommons.org