Associative Parallel Algorithms for Dynamic Edge Update of Minimum Spanning Trees

Autor:	Anna Nepomniaschaya
Rok vydání:	2003
Předmět:	Spanning tree Computer science Parallel algorithm Graph (abstract data type) Parallel computing SIMD Minimum spanning tree Time complexity Algorithm Graph Associative property
Zdroj:	Lecture Notes in Computer Science ISBN: 9783540406730 PaCT
Popis:	In this paper we propose two associative parallel algorithms for the edge update of a minimum spanning tree when an edge is deleted or inserted in the underlying graph. These algorithms are represented as the corresponding procedures implemented on a model of associative parallel systems of the SIMD type with vertical data processing (the STAR–machine). We justify correctness of these procedures and evaluate their time complexity.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::408014f2b64ae71fd7d451127c4934b3 https://doi.org/10.1007/978-3-540-45145-7_12 Zobrazit plný text záznamu