Title :
Associative parallel algorithms for computing functions defined on paths in trees
Author :
Nepomniaschaya, A.S.
Author_Institution :
Inst. of Computational Math. & Math. Geophys., Russian Acad. of Sci., Novosibirsk, Russia
Abstract :
By means of an abstract model of the SIMD type with vertical data processing (the STAR-machine), we present a simple associative parallel algorithm for finding tree paths in undirected graphs. We study applications of this algorithm to update minimum spanning trees in undirected graphs, to determine maximum flow values in a multiterminal network, and to find a fundamental set of circuits with respect to a given spanning tree. These algorithms are given as the corresponding STAR procedures whose correctness is proved and time complexity is evaluated.
Keywords :
computational complexity; parallel algorithms; trees (mathematics); SIMD type abstract model; STAR machine; associative parallel algorithms; circuits; correctness proving; maximum flow values; minimum spanning tree update; multiterminal network; spanning tree; time complexity; tree paths; undirected graphs; vertical data processing; Associative processing; Concurrent computing; Data processing; Electronic mail; Geophysics computing; Mathematics; Parallel algorithms; Parallel processing; Registers; Tree graphs;
Conference_Titel :
Parallel Computing in Electrical Engineering, 2002. PARELEC '02. Proceedings. International Conference on
Print_ISBN :
0-7695-1730-7
DOI :
10.1109/PCEE.2002.1115307
