Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree
The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable)...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Yaroslavl State University
2013-04-01
|
| Series: | Моделирование и анализ информационных систем |
| Subjects: | |
| Online Access: | https://www.mais-journal.ru/jour/article/view/202 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849240809225846784 |
|---|---|
| author | A. S. Nepomniaschaya |
| author_facet | A. S. Nepomniaschaya |
| author_sort | A. S. Nepomniaschaya |
| collection | DOAJ |
| description | The paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable) parallel systems with simple single–bit processing elements and vertical processing. The associative algorithm is represented on the STAR–machine as the main procedure DeleteArcSPT that uses some auxiliary procedures. By means of the auxiliary procedures, we execute some parts of the associative parallel algorithm for dynamic update of the shortest paths tree after deleting an arc from the graph. We prove correctness of the procedure DeleteArcSPT and all its parts. We obtain that on the STAR–machine this procedure takes O(hk) time, where h is the number of bits required for coding the maximum of the shortest paths weights and k is the number of vertices, whose shortest paths change after deleting an edge from the given graph. |
| format | Article |
| id | doaj-art-7c27badecd5446fa827d415adf3986a3 |
| institution | Kabale University |
| issn | 1818-1015 2313-5417 |
| language | English |
| publishDate | 2013-04-01 |
| publisher | Yaroslavl State University |
| record_format | Article |
| series | Моделирование и анализ информационных систем |
| spelling | doaj-art-7c27badecd5446fa827d415adf3986a32025-08-20T04:00:26ZengYaroslavl State UniversityМоделирование и анализ информационных систем1818-10152313-54172013-04-0120252210.18255/1818-1015-2013-2-5-22196Associative Parallel Algorithm for Dynamic Update of the Shortest Paths TreeA. S. Nepomniaschaya0Institute of Computational Mathematics and Mathematical Geophysics SB RASThe paper proposes an efficient associative algorithm for dynamic update of the shortest paths tree of a directed weighted graph after deleting an edge. To this end, we provide the data structure and its building along with the STAR–machine that simulates the run of associative (content–addressable) parallel systems with simple single–bit processing elements and vertical processing. The associative algorithm is represented on the STAR–machine as the main procedure DeleteArcSPT that uses some auxiliary procedures. By means of the auxiliary procedures, we execute some parts of the associative parallel algorithm for dynamic update of the shortest paths tree after deleting an arc from the graph. We prove correctness of the procedure DeleteArcSPT and all its parts. We obtain that on the STAR–machine this procedure takes O(hk) time, where h is the number of bits required for coding the maximum of the shortest paths weights and k is the number of vertices, whose shortest paths change after deleting an edge from the given graph.https://www.mais-journal.ru/jour/article/view/202directed weighted graph$the shortest paths treeadjacency matrixdecremental algorithmassociative parallel processor |
| spellingShingle | A. S. Nepomniaschaya Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree Моделирование и анализ информационных систем directed weighted graph$ the shortest paths tree adjacency matrix decremental algorithm associative parallel processor |
| title | Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree |
| title_full | Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree |
| title_fullStr | Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree |
| title_full_unstemmed | Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree |
| title_short | Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree |
| title_sort | associative parallel algorithm for dynamic update of the shortest paths tree |
| topic | directed weighted graph$ the shortest paths tree adjacency matrix decremental algorithm associative parallel processor |
| url | https://www.mais-journal.ru/jour/article/view/202 |
| work_keys_str_mv | AT asnepomniaschaya associativeparallelalgorithmfordynamicupdateoftheshortestpathstree |