A parallel fully dynamic iterative Bio-Inspired Shortest Path Algorithm

Basit Öğe Kaydı
dc.authoridArslan, Hilal / 0000-0002-6449-6952
dc.authorscopusid55612037400
dc.authorwosidArslan, Hilal/AAQ-8217-2020
dc.authorwosidArslan, Hilal/ABI-7754-2020
dc.contributor.authorArslan, Hilal
dc.date.accessioned2022-02-15T16:57:19Z
dc.date.available2022-02-15T16:57:19Z
dc.date.issued2020
dc.departmentBakırçay Üniversitesien_US
dc.description.abstractWe propose a fully dynamic bio-inspired parallel algorithm for solving the shortest path problem on dynamically changing graphs based on Physarum Solver, which is an amoeba shortest path algorithm. Although many sequential algorithms exist for solving dynamic shortest path problem, there are only few parallel algorithms, most of which identify the set of vertices affected by the dynamic changes. However, when the graph size becomes large, the process of determining affected vertices is time-consuming. In fact, when the percentage of changing edges is large, most of the studies in the literature are infeasible. The proposed algorithm is able to identify affected vertices and reconstruct them spontaneously in parallel. Moreover, it is designed to be suitable for dynamically changing graphs since it uses the information arising in earlier iterations. Thus, it computes effectively dynamic shortest path even if percentage of changing edges is large. At each iteration of the proposed algorithm, a sparse linear system of equations needs to be solved, which is the most time-consuming and challenging step of the algorithm especially when the problem size is large. We propose a parallel preconditioned iterative method for solving those sparse linear systems. The proposed preconditioner is specifically designed based on the properties of the coefficient matrix of those linear systems, and the effectiveness of the proposed preconditioner is compared against other state-of-the-art preconditioners on dynamic graphs. The proposed algorithm is evaluated using three different large graph models representing diverse real-life applications on a parallel multicore cluster. The parallel scalability of the proposed algorithm is compared against Delta-stepping, which is the most representative parallel implementation of Dijkstra's algorithm in the Parallel Boost Graph Library.en_US
dc.identifier.doi10.1007/s13369-020-04606-3
dc.identifier.endpage10130en_US
dc.identifier.issn2193-567X
dc.identifier.issn2191-4281
dc.identifier.issue12en_US
dc.identifier.scopus2-s2.0-85085347526en_US
dc.identifier.scopusqualityQ1en_US
dc.identifier.startpage10115en_US
dc.identifier.urihttps://doi.org/10.1007/s13369-020-04606-3
dc.identifier.urihttps://hdl.handle.net/20.500.14034/98
dc.identifier.volume45en_US
dc.identifier.wosWOS:000535102800003en_US
dc.identifier.wosqualityQ3en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.institutionauthorArslan, Hilal
dc.language.isoenen_US
dc.publisherSpringer Heidelbergen_US
dc.relation.journalArabian Journal For Science And Engineeringen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectPhysarum solveren_US
dc.subjectParallel dynamic shortest pathen_US
dc.subjectM-matrixen_US
dc.subjectParallel sparse iterative solversen_US
dc.subjectPreconditioningen_US
dc.subjectTree Computationen_US
dc.subjectNetworken_US
dc.subjectImplementationen_US
dc.subjectConvergenceen_US
dc.subjectDesignen_US
dc.titleA parallel fully dynamic iterative Bio-Inspired Shortest Path Algorithmen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
[ X ]
İsim:
A Parallel Fully Dynamic Iterative Bio-Inspired Shortest Path Algorithm.pdf
Boyut:
719.87 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Tam Metin / Full Text
İndir

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Bilgisayar Mühendisliği Bölümü Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu