Árbol de caminos mínimos: enrutamiento, algoritmos aproximados y complejidad

Efren  Romero Riaño; Gabriel Mauricio  Martínez Toro; Dewar  Rico Bautista

doi:10.24054/rcta.v1i31.123

Authors

Efren Romero Riaño Universidad Manuela Beltrán1
Gabriel Mauricio Martínez Toro Universidad Autónoma de Bucaramanga
Dewar Rico Bautista Universidad Francisco de Paula Santander

DOI:

https://doi.org/10.24054/rcta.v1i31.123

Keywords:

Complejidad computacional, MST, NP-HARD, NPSPACE, PSPACE

Abstract

El documento aborda la temática relacionada con los algoritmos aproximados como método para solución de problemas computacionalmente complejos. El objetivo de este paper, es presentar un análisis comparativo entre tres enfoques clásicos de solución de algoritmos y el enfoque de solución mediante algoritmos aproximados. Este análisis incluye la descripción de los códigos y pseudocódigos, así como su análisis comparativo en términos de complejidad en tiempo y espacio. La metodología implementada fue de revisión basada en indicadores biblio métricos de las fuentes y posterior análisis de contenido de los documentos seleccionados. La complejidad computacional de los algoritmos analizados se puede dividir en complejidad de tiempo y de espacio, cada una de estas agrupan los problemas según sus características dentro de los grupos P, NP, PSPACE, NPSPACE, entre otros. A través de la reducción del Set Cover Problem en una versión del Minimun Spanning Tree, MST, se logró comprobar la complejidad de este problema de conectividad. La eficiencia de los algoritmos se determinó con base en los recursos que son utilizados en el momento en que son ejecutados. Se presenta un paralelo entre algoritmos aproximados y algoritmos alternativos a la luz del ejemplo de la reducción del set cover en un árbol de expansión mínimo, logrando evidenciar la complejidad en algoritmos de conectividad. La complejidad computacional se mide a la luz del uso de los recursos, bien sea el uso de los recursos de tiempo o espacio, generando clasificaciones de problemas según sus características particulares medidas por estos dos parámetros.

Downloads

Download data is not yet available.

References

Araque, J., Díaz, J., & Gualdrón, O. (2013). Optimización del thd en un convertidor multinivel monofásico usando algoritmos genéticos. Revista Colombiana Tecnologías de Avanzada , 1(21), 60-66. doi:https://doi.org/10.24054/16927257.v21.n21.2013.297

Ariganello, E. (2014). Redes Cisco. Guía de estudio para la certificación. CCNA Routing y switching (Primera ed.). México D.F., México: Alfaomega. Recuperado el 15 de Mayo de 2017

Barbehenn, M. (1998). A note on the complexity of Dijkstra’s algorithm for graphs with weighted vertices. IEEE Transactions on Computers, 47(2), 263. https://doi.org/10.1109/12.663776

Bollobás, B., & Riordan, O. (1993). Dijkstra â€TM s Algorithm. Network, 69(1959), 36114. Retrieved from http://www.ncbi.nlm.nih.gov/pubmed/21282851

Duarte Muñoz, A. (2007). Metaheuristicas. Madrid: Dykinson.

Fan, D., & Shi, P. (2010). Improvement of Dijkstra’s algorithm and its application in route planning. 2010 Seventh International Conference on Fuzzy Systems and Knowledge Discovery. https://doi.org/10.1109/FSKD.2010.5569452

Frederickson, G. N., Hecht, M. S., & Kim, C. E. (1976). Approximation agorithms for some routing problems. 17th Annual Symposium on Foundations of Computer Science (Sfcs 1976), 7(2), 178–193. https://doi.org/10.1109/SFCS.1976.6

Garroppo, R. G., Giordano, S., & Tavanti, L. (2010). A survey on multi-constrained optimal path computation: Exact and approximate algorithms. Computer Networks, 54(17), 3081–3107. https://doi.org/10.1016/j.comnet.2010.05.017

Gupta, A., & Könemann, J. (2011). Approximation algorithms for network design: A survey. Surveys in Operations Research and Management Science, 16(1), 3–20. https://doi.org/10.1016/j.sorms.2010.06.001

Klinkowski, M., & Walkowiak, K. (2016). On the complexity of routing and spectrum allocation in survivable elastic optical network with unicast and anycast traffic. International Workshop on Resilient Networks Design and Modeling (RNDM). Halmstad: IEEE. doi:10.1109/RNDM.2016.7608283

Laporte, G., & Osman, I. H. (1995). Routing problems: A bibliography. Annals of Operations Research, 61(1), 227–262. https://doi.org/10.1007/BF02098290

Levin, L., Kowalski, D. R., & Segal, M. (2015). Message and time efficient multi-broadcast schemes. Theoretical Computer Science, 569, 13–23. https://doi.org/10.1016/j.tcs.2014.12.006

Medina Cárdenas, Y., & Rico Bautista, D. (2008). Modelo de gestión de servicios para la universidad de Pamplona: ITIL. Scientia Et Technica, XIV (39), 314-319.

Medina Cárdenas, Y., & Rico Bautista, D. (2009). Modelo de gestión basado en el ciclo de vida del servicio de la Biblioteca de Infraestructura de Tecnologías de Información (ITIL). Revista Virtual Universidad Católica del Norte, (27), 1-21.

Medina, Y., Rico, D., & Areniz, Y. (2016). Modelo estratégico para la gestión tecnológica en la organización: plan táctico de la calidad (ITIL & ISO 20000). (I. T. Metropolitano, Ed.) Ocaña: Fondo Editorial ITM. doi:https://doi.org/10.22430/9789585414006

Méndez, L., Rodriguez-Colina, E., & Medina, C. (2014). Toma de Decisiones Basadas en el Algoritmo de DIJKSTRA. Redes de Ingeniería, 4(2), 2013. Retrieved from http://revistas.udistrital.edu.co/ojs/index.php/REDES/article/view/6357/7872

Parra, C., & Herrera, J. (2013). Aplicación de los sistemas de detección de intrusos y la tecnología de agentes en el monitoreo inteligente de redes de datos. Revista Colombiana de Tecnologías de Avanzada, 106-110. doi:https://doi.org/10.24054/16927257.v22.n22.2013.417

Patiño, N., Moreno, M., & Toro, E. (2013). Modelamiento matemático del problema de ocupación de quirófanos. Revista Colombiana Tecnologías de Avanzada, 2(20), 43-49. doi:https://doi.org/10.24054/16927257.v20.n20.2012.187

Rojas, M., & Sánchez, M. (2012). Arquitectura de software para el servicio de soporte de tecnología de información basada en servicios web. Revista Colombiana Tecnologías de Avanzada, 2(20), 144-150. doi:https://doi.org/10.24054/16927257.v20.n20.2012.201

Rodriguéz Gálvez, M. D. (Enero de 2009). Problemas de Optimozación en Arboles Generadores. Trabajo de fin de carrera. Madrid.

Santos, L., & Flórez, A. (2013). Metodología para el análisis forense en linux. Revista Colombiana Tecnologías de Avanzada, 2(20), 90-96. doi:https://doi.org/10.24054/16927257.v20.n20.2012.194

Siachalou, S., & Georgiadis, L. (2003). Efficient QoS routing. Computer Networks, 43(3), 351–367. https://doi.org/10.1016/S1389-1286(03)00286-X

Skiena, S. (1982). The Algorithm Design Manual Second Edition. Department of Computer Science State University of New York at Stony Brook New York, USA.

Universidad de los Andes. (2016). Diseño y Análisis de algoritmos. DISC – Departamento de Ingeniería de Sistemas y Computación. Recuperado el 15 de Mayo de 2017, de https://cursos.virtual.uniandes.edu.co/isis1105/

Vazirani, V. V. (2003). Approximation Algorithms. Berlin: Springer.

Williamson, D. P., & Shmoys, D. B. (2 de 2 de 2011). The Design of Approximation Algoritms. Cambridge: Cambridge University Press.

Yin, C., & Wang, H. (2010). Developed Dijkstra shortest path search algorithm and simulation. In 2010 International Conference on Computer Design and Applications, ICCDA 2010 (Vol. 1). https://doi.org/10.1109/ICCDA.2010.5541129