| Revue: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000373013 |
| ISSN: | 1405-5546 |
| Autores: | Rodríguez Puente, Rafael1 Lazo Cortés, Manuel S1 |
| Instituciones: | 1Universidad de las Ciencias Informáticas, La Habana. Cuba |
| Año: | 2014 |
| Periodo: | Ene-Mar |
| Volumen: | 18 |
| Número: | 1 |
| Paginación: | 185-194 |
| País: | México |
| Idioma: | Español |
| Tipo de documento: | Artículo |
| Enfoque: | Experimental, aplicado |
| Resumen en español | 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, contribuyendo a la obtención de respuestas óptimas en tiempos menores |
| Resumen en inglés | Algorithms related to graph theory have been studied widely. Several studies deal with the reduction of temporal complexity of these algorithms. The techniques used in this sense are generally based on reducing the graph or the search space of solution. These approaches remove redundant information for a specific kind of problem. The process of reducing a graph is based on obtaining smaller graphs (with fewer vertices) with major or relevant characteristics of the original graph. Algorithms that make use of the graph reduction approach (or reduction of solution search space) for the shortest path search do not guarantee obtaining an optimal path in all cases. The same applies to other types of problems such as graph reduction in workflow networks, computer networks, etc. In this paper we propose a graph reduction algorithm without loss of information. Our method is characterized by a flexible way to specify in what manner in it desirable to reduce a given graph. Therefore, our proposal can be used in solving various types of problems and obtaining optimal responses in less time |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Procesamiento de datos, Reducción de grafos, Algoritmos, Complejidad algorítmica |
| Keyword: | Computer science, Data processing, Graph reduction, Algorithms, Algorithm complexity |
| Texte intégral: | Texto completo (Ver HTML) |
