Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark

La escalonabilidad* de grafos es un problema en NP del que se desconoce su inclusión en las clases de complejidad P o NP-completa. Con el fin de comprender su comportamiento computacional en el caso particular de los grafos bipartitos, podría ser de utilidad disponer de un método eficiente para generar y analizar instancias escalonables. La literatura reporta un experimento secuencial, y de costo exponencial, diseñado para determinar la escalonabilidad de un conjunto de instancias. En el presente trabajo, y con el fin de mejorar el desempeño experimento mencionado, proponemos tres alternativas utilizando Apache Spark: una multinúcleo, otra multinodo y otra completamente paralela. Además, comparamos el tiempo de ejecución de cada una de ellas respecto a la versión original en grafos bipartitos aleatorios con 10,12,15,20 y 50 vértices, y obtuvimos aceleraciones (speedups) entre 1.37 y 1.67 para la versión multinúcleo, entre 2.34 y 3.56 para la versión multinodo, y entre 2.37 y 3.12 para la versión completamente paralela. Los resultados sugieren que la paralelización del experimento podría mitigar los enormes tiempos de ejecución del enfoque original.

• Autores: Arango Holguín, Julián David; Cárdenas Álzate, Milena; Santamaría Galvis, Andrés David
• Tipo de recurso: Article of journal
• Fecha de publicación: 2017
• Institución: Universidad de los Llanos
• Repositorio: Repositorio Digital Universidad de los LLanos
• Idioma: eng
• OAI Identifier: oai:repositorio.unillanos.edu.co:001/2650
• Acceso en línea: https://repositorio.unillanos.edu.co/handle/001/2650; https://doi.org/10.22579/20112629.428
• Palabra clave: Editorial; Editorial
• Rights: openAccess
• License: Orinoquia - 2019