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

Authors

  • Rafael Rodríguez Puente et al.

Abstract

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.

Downloads

Download data is not yet available.

Downloads

Published

2014-12-18

How to Cite

Rodríguez Puente et al., R. (2014). Reducción de grafos sin pérdida de información. Anales De La Academia De Ciencias De Cuba. Retrieved from https://revistaccuba.sld.cu/index.php/revacc/article/view/138

Issue

Vol.4 No.2 2014

Section

Natural and Exact Sciences

License

The journal Anales de la Academia de Ciencias de Cuba protects copyright, and operates with a Creative Commons License 4.0 (Creative Commons Attribution-NonCommercial License 4.0). By publishing in it, authors allow themselves to copy, reproduce, distribute, publicly communicate their work and generate derivative works, as long as the original author is cited and acknowledged. They do not allow, however, the use of the original work for commercial or lucrative purposes.

The authors authorize the publication of their writings, retaining the authorship rights, and assigning and transferring to the magazine all the rights protected by the intellectual property laws that govern in Cuba, which imply editing to disseminate the work.

Authors may establish additional agreements for the non-exclusive distribution of the version of the work published in the journal (for example, placing it in an institutional repository or publishing it in a book), with recognition of having been first published in this journal.

To learn more, see https://creativecommons.org