Graph Reduction Algorithm without Loss of Information

Graph Reduction Algorithm without Loss of Information

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...

Saved in:
Translated title: Algoritmo de reducci贸n de grafos sin p茅rdida de informaci贸n
Journal Title: Computaci贸n y Sistemas
First author: Rafael Rodr铆guez Puente
Other Authors: Manuel Sabino Lazo Cort茅s
Traslated keyword:
Language: Undetermined
Get full text: http://www.cys.cic.ipn.mx/ojs/index.php/CyS/article/view/1574
Resource type: Journal Article
Source: Computaci贸n y Sistemas; Vol 18, No 1 (Year 2014).
DOI: http://dx.doi.org/10.13053/cys-18-1-1574
Publisher: Instituto Polit茅cnico Nacional
Usage rights: Otros Queda prohibida la reproducci贸n total o parcial de los contenidos e im谩genes de la difusi贸n sin previa autorizaci贸n del Instituto Polit茅cnico Nacional
Categories: Physical/Engineering Sciences --> Computer Science, Information Systems
Abstract: 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.
Translated 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, contribuyendo a la obtenci贸n de respuestas 贸ptimas en tiempos menores.