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 gene...
- 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
| id |
Unillanos2_c018f7d2a678108d510581f8e88b5184 |
|---|---|
| oai_identifier_str |
oai:repositorio.unillanos.edu.co:001/2650 |
| network_acronym_str |
Unillanos2 |
| network_name_str |
Repositorio Digital Universidad de los LLanos |
| repository_id_str |
|
| dc.title.spa.fl_str_mv |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| dc.title.translated.eng.fl_str_mv |
Parallelizing an experiment to decide shellability on bipartite graphs using Apache Spark |
| title |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| spellingShingle |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark Editorial Editorial |
| title_short |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| title_full |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| title_fullStr |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| title_full_unstemmed |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| title_sort |
Paralelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache Spark |
| dc.creator.fl_str_mv |
Arango Holguín, Julián David Cárdenas Álzate, Milena Santamaría Galvis, Andrés David |
| dc.contributor.author.spa.fl_str_mv |
Arango Holguín, Julián David Cárdenas Álzate, Milena Santamaría Galvis, Andrés David |
| dc.subject.spa.fl_str_mv |
Editorial |
| topic |
Editorial Editorial |
| dc.subject.eng.fl_str_mv |
Editorial |
| description |
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. |
| publishDate |
2017 |
| dc.date.accessioned.none.fl_str_mv |
2017-07-16 00:00:00 2022-06-13T17:42:07Z |
| dc.date.available.none.fl_str_mv |
2017-07-16 00:00:00 2022-06-13T17:42:07Z |
| dc.date.issued.none.fl_str_mv |
2017-07-16 |
| dc.type.spa.fl_str_mv |
Artículo de revista |
| dc.type.eng.fl_str_mv |
Journal Article |
| dc.type.coar.fl_str_mv |
http://purl.org/coar/resource_type/c_2df8fbb1 |
| dc.type.driver.eng.fl_str_mv |
info:eu-repo/semantics/article |
| dc.type.local.spa.fl_str_mv |
Sección Artículos |
| dc.type.local.eng.fl_str_mv |
Sección Articles |
| dc.type.version.eng.fl_str_mv |
info:eu-repo/semantics/publishedVersion |
| dc.type.coar.eng.fl_str_mv |
http://purl.org/coar/resource_type/c_6501 |
| dc.type.content.eng.fl_str_mv |
Text |
| dc.type.coarversion.eng.fl_str_mv |
http://purl.org/coar/version/c_970fb48d4fbd8a85 |
| format |
http://purl.org/coar/resource_type/c_6501 |
| status_str |
publishedVersion |
| dc.identifier.issn.none.fl_str_mv |
0121-3709 |
| dc.identifier.uri.none.fl_str_mv |
https://repositorio.unillanos.edu.co/handle/001/2650 |
| dc.identifier.doi.none.fl_str_mv |
10.22579/20112629.428 |
| dc.identifier.eissn.none.fl_str_mv |
2011-2629 |
| dc.identifier.url.none.fl_str_mv |
https://doi.org/10.22579/20112629.428 |
| identifier_str_mv |
0121-3709 10.22579/20112629.428 2011-2629 |
| url |
https://repositorio.unillanos.edu.co/handle/001/2650 https://doi.org/10.22579/20112629.428 |
| dc.language.iso.eng.fl_str_mv |
eng |
| language |
eng |
| dc.relation.references.eng.fl_str_mv |
Björner A, Wachs ML. Shellable Nonpure Complexes and Posets I. Trans. Amer. Math. Soc. 1996;348(4):1299-1327. Castrillón ID, Cruz R.). Escalonabilidad de grafos e hipergrafos simples que contienen vértices simpliciales. Matemáticas: Enseñanza Universitaria. 2012;20(1):29-80. Cruz R, Estrada M. Vértices simpliciales y escalonabilidad de grafos. Morfismos. 2008;12:21-36. Csárdi G, Nepusz T. 2006. The igraph software package for complex network research. InterJournal Complex Systems. Retrieved from http://igraph.sf.net Csárdi G, Nepusz T. (2012, June). The igraph software package for complex network research, (ver. 0.6). Retrieved from http://igraph.sf.net Hadoop®, A. 2016. The Apache® Software Foundation. Retrieved from The Apache® Software Foundation: http://hadoop.apache.org/ Hennessy JL, Patterson DA. 2012. Computer Architecture: A Quantitative Approach. 5th ed. Elsevier - Morgan Kaufmann. Herlihy M. 2010. Applications of Shellable Complexes to Distributed Computing. CONCUR (pp. 19-20). Springer. Herlihy M, Rajsbaum S. 2010. Concurrent Computing and Shellable Complexes. DISC (pp. 109-123). Springer. Kaibel V, Pfetsch ME. 2003. Some Algorithmic Problems in Polytope Theory. Algebra, Geometry, and Software Systems (outcome of a Dagstuhl Seminar) (pp. 23-47). Springer-Verlag. Lewiner T. 2005. Complexos de Morse discretos e geométricos. master's thesis. Rio de Janeiro. Müller-Hannemann M. Shelling Hexahedral Complexes for Mesh Generation. Journal of Graph Algortihms and Applications, 2001;5(5):59-91. Santamaria-Galvis AD. 2013. On Algorithmic Complexity of Shellability in Graphs and their Associated Simplicial Complexes. Master's thesis, Facultad de Minas, Universidad Nacional de Colombia, Medellin, Colombia, Medellín. Schläfli L. (1901, January). Theorie der vielfachen Kontinuität; hrsg. im Auftrage der Denkschriften_Kommission der Schweizer. Naturforschenden Gesellschaft. Zürich: Zürcher & Furrer. Spark™ A. 2016. Apache Spark™ Lightning-fast cluster computing. (The Apache® Software Foundation) Retrieved from Apache Spark™ Lightning-fast cluster computing: http://spark.apache.org/ Van Tuyl A, Villarreal RH. Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. J. Combin. Theory Ser. A, 2008;115(5):799-814. Woodroofe R. Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 2009;137(10):3235-3246. |
| dc.relation.bitstream.none.fl_str_mv |
https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/428/1019 |
| dc.relation.citationedition.spa.fl_str_mv |
Núm. 1 Sup , Año 2017 |
| dc.relation.citationendpage.none.fl_str_mv |
36 |
| dc.relation.citationissue.spa.fl_str_mv |
1 Sup |
| dc.relation.citationstartpage.none.fl_str_mv |
30 |
| dc.relation.citationvolume.spa.fl_str_mv |
21 |
| dc.relation.ispartofjournal.spa.fl_str_mv |
Orinoquia |
| dc.rights.eng.fl_str_mv |
Orinoquia - 2019 |
| dc.rights.uri.eng.fl_str_mv |
https://creativecommons.org/licenses/by/4.0/ |
| dc.rights.accessrights.eng.fl_str_mv |
info:eu-repo/semantics/openAccess |
| dc.rights.coar.eng.fl_str_mv |
http://purl.org/coar/access_right/c_abf2 |
| rights_invalid_str_mv |
Orinoquia - 2019 https://creativecommons.org/licenses/by/4.0/ http://purl.org/coar/access_right/c_abf2 |
| eu_rights_str_mv |
openAccess |
| dc.format.mimetype.eng.fl_str_mv |
application/pdf |
| dc.publisher.spa.fl_str_mv |
Universidad de los Llanos |
| dc.source.eng.fl_str_mv |
https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/428 |
| institution |
Universidad de los Llanos |
| bitstream.url.fl_str_mv |
https://dspace7-unillanos.metacatalogo.org/bitstreams/b795d07a-8f4a-4315-ad6f-33370d740587/download |
| bitstream.checksum.fl_str_mv |
f08303c9529bba4da10fb07934b6cc5e |
| bitstream.checksumAlgorithm.fl_str_mv |
MD5 |
| repository.name.fl_str_mv |
Repositorio Universidad de Los Llanos |
| repository.mail.fl_str_mv |
repositorio@unillanos.edu.co |
| _version_ |
1812104656293199872 |
| spelling |
Arango Holguín, Julián David5368a7fa61435a0e4d58cc6258553408300Cárdenas Álzate, Milena0ade1d0ec3ed3a6b6584e9bef4432f80300Santamaría Galvis, Andrés David16e1f4586ee0f02d9a218e8447a5811f3002017-07-16 00:00:002022-06-13T17:42:07Z2017-07-16 00:00:002022-06-13T17:42:07Z2017-07-160121-3709https://repositorio.unillanos.edu.co/handle/001/265010.22579/20112629.4282011-2629https://doi.org/10.22579/20112629.428La 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.Graph shellability is an NP problem whose classification either in P or in NP-complete remains unknown. In order to understand the computational behavior of graph shellability on bipartite graphs, as a particular case, it could be useful to develop an efficient way to generate and analyze results over sets of shellable and non-shellable instances. In this way, a sequentially designed exponential time experiment for deciding shellability on randomly generated instances was proposed in literature. In this work, with the aim of improving the performance of that experiment, we propose three alternative approaches using Apache Spark™, we called multi-core, multi-node and full-parallel. We tested and compared their execution time for bipartite graphs with 10,12,15,20 and 50 vertices with regard to the original version, and we got speedups between 1.37 and 1.67 for the first one, between 2.34 and 3.56 for the second one, and between 2.37 y 3.12 for the last version. The results suggest that parallelization could relieve the large execution times of the original approach.application/pdfengUniversidad de los LlanosOrinoquia - 2019https://creativecommons.org/licenses/by/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/view/428EditorialEditorialParalelización de un experimento para determinar la escalonabilidad de grafos bipartitos usando Apache SparkParallelizing an experiment to decide shellability on bipartite graphs using Apache SparkArtículo de revistaJournal Articleinfo:eu-repo/semantics/articleSección ArtículosSección Articlesinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1Texthttp://purl.org/coar/version/c_970fb48d4fbd8a85Björner A, Wachs ML. Shellable Nonpure Complexes and Posets I. Trans. Amer. Math. Soc. 1996;348(4):1299-1327.Castrillón ID, Cruz R.). Escalonabilidad de grafos e hipergrafos simples que contienen vértices simpliciales. Matemáticas: Enseñanza Universitaria. 2012;20(1):29-80.Cruz R, Estrada M. Vértices simpliciales y escalonabilidad de grafos. Morfismos. 2008;12:21-36.Csárdi G, Nepusz T. 2006. The igraph software package for complex network research. InterJournal Complex Systems. Retrieved from http://igraph.sf.netCsárdi G, Nepusz T. (2012, June). The igraph software package for complex network research, (ver. 0.6). Retrieved from http://igraph.sf.netHadoop®, A. 2016. The Apache® Software Foundation. Retrieved from The Apache® Software Foundation: http://hadoop.apache.org/Hennessy JL, Patterson DA. 2012. Computer Architecture: A Quantitative Approach. 5th ed. Elsevier - Morgan Kaufmann.Herlihy M. 2010. Applications of Shellable Complexes to Distributed Computing. CONCUR (pp. 19-20). Springer.Herlihy M, Rajsbaum S. 2010. Concurrent Computing and Shellable Complexes. DISC (pp. 109-123). Springer.Kaibel V, Pfetsch ME. 2003. Some Algorithmic Problems in Polytope Theory. Algebra, Geometry, and Software Systems (outcome of a Dagstuhl Seminar) (pp. 23-47). Springer-Verlag.Lewiner T. 2005. Complexos de Morse discretos e geométricos. master's thesis. Rio de Janeiro.Müller-Hannemann M. Shelling Hexahedral Complexes for Mesh Generation. Journal of Graph Algortihms and Applications, 2001;5(5):59-91.Santamaria-Galvis AD. 2013. On Algorithmic Complexity of Shellability in Graphs and their Associated Simplicial Complexes. Master's thesis, Facultad de Minas, Universidad Nacional de Colombia, Medellin, Colombia, Medellín.Schläfli L. (1901, January). Theorie der vielfachen Kontinuität; hrsg. im Auftrage der Denkschriften_Kommission der Schweizer. Naturforschenden Gesellschaft. Zürich: Zürcher & Furrer.Spark™ A. 2016. Apache Spark™ Lightning-fast cluster computing. (The Apache® Software Foundation) Retrieved from Apache Spark™ Lightning-fast cluster computing: http://spark.apache.org/Van Tuyl A, Villarreal RH. Shellable graphs and sequentially Cohen-Macaulay bipartite graphs. J. Combin. Theory Ser. A, 2008;115(5):799-814.Woodroofe R. Vertex decomposable graphs and obstructions to shellability. Proc. Amer. Math. Soc. 2009;137(10):3235-3246.https://orinoquia.unillanos.edu.co/index.php/orinoquia/article/download/428/1019Núm. 1 Sup , Año 2017361 Sup3021OrinoquiaPublicationOREORE.xmltext/xml2607https://dspace7-unillanos.metacatalogo.org/bitstreams/b795d07a-8f4a-4315-ad6f-33370d740587/downloadf08303c9529bba4da10fb07934b6cc5eMD51001/2650oai:dspace7-unillanos.metacatalogo.org:001/26502024-04-17 16:40:26.176https://creativecommons.org/licenses/by/4.0/Orinoquia - 2019metadata.onlyhttps://dspace7-unillanos.metacatalogo.orgRepositorio Universidad de Los Llanosrepositorio@unillanos.edu.co |