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

fYear

2002

fDate

2002

Firstpage

399

Lastpage

404

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Computing in Electrical Engineering, 2002. PARELEC '02. Proceedings. International Conference on

Print_ISBN

0-7695-1730-7

Type

conf

DOI

10.1109/PCEE.2002.1115307

Filename

1115307