Modelirovanie i Analiz Informatsionnykh Sistem
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Model. Anal. Inform. Sist.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Modelirovanie i Analiz Informatsionnykh Sistem, 2013, Volume 20, Number 2, Pages 5–22 (Mi mais294)  

This article is cited in 1 scientific paper (total in 1 paper)

Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree

A. Sh. Nepomniaschaya

Institute of Computational Mathematics and Mathematical Geophysics SB RAS, prospect Akademika Lavrentjeva 6, Novosibirsk, 630090, Russia
Full-text PDF (189 kB) Citations (1)
References:
Abstract: 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.
Keywords: directed weighted graph, the shortest paths tree, adjacency matrix, decremental algorithm, associative parallel processor.
Received: 19.04.2012
Document Type: Article
UDC: 519.172
Language: Russian
Citation: A. Sh. Nepomniaschaya, “Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree”, Model. Anal. Inform. Sist., 20:2 (2013), 5–22
Citation in format AMSBIB
\Bibitem{Nep13}
\by A.~Sh.~Nepomniaschaya
\paper Associative Parallel Algorithm for Dynamic Update of the Shortest Paths~Tree
\jour Model. Anal. Inform. Sist.
\yr 2013
\vol 20
\issue 2
\pages 5--22
\mathnet{http://mi.mathnet.ru/mais294}
Linking options:
  • https://www.mathnet.ru/eng/mais294
  • https://www.mathnet.ru/eng/mais/v20/i2/p5
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Моделирование и анализ информационных систем
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024