Please use this identifier to cite or link to this item: http://repositorio.ufpso.edu.co/jspui/handle/123456789/3572
Title: Minimum path tree: routing, approximate algorithms and complexity
Authors: Romero Riaño, Efren
Martínez Toro, Gabriel Mauricio
Rico-Bautista, Dewar
Romero Riaño, Efren [0001423333]
Romero Riaño, Efren [iduK4zEAAAAJ]
Romero Riaño, Efren [0000-0002-3627-9942]
Romero Riaño, Efren [Efren-Riano]
Romero Riaño, Efren [57205706551]
Keywords: Complejidad computacional
MST
NP-HARD
NPSPACE
PSPACE
Issue Date: 22-Jun-2018
Citation: Romero Riaño, E., Martínez Toro, G. M., Rico-Bautista, D. Árbol de caminos mínimos: enrutamiento, algoritmos aproximados y complejidad. Revista Colombiana de Tecnologías de Avanzada v.1 no. 31 2018. Recuperado de: https://doi.org/10.24054/16927257.v31.n31.2018.2780
Series/Report no.: GRIITEM;ART01
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.
URI: http://repositorio.ufpso.edu.co/jspui/handle/123456789/3572
ISSN: 692-7257
Appears in Collections:Artículos

Files in This Item:
File Description SizeFormat 
2018_Articulo_Efren_Romero_Riano.pdfArtículo639,34 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.