Title :
An associative parallel algorithm for finding a critical cycle in directed graphs
Author :
Nepomniaschaya, A.S.
Author_Institution :
Inst. of Comput. Math. & Math. Geophys., Acad. of Sci., Novosibirsk, Russia
Abstract :
In this paper, we propose a novel associative parallel algorithm for selecting a critical cycle in directed weighted graphs by means of an abstract model of the SIMD type with vertical data processing (the STAR-machine). This problem arises when performing J. Edmonds´ (1967) algorithm for finding optimum branchings. This algorithm is represented as the corresponding STAR procedure whose correctness is verified and whose time complexity is evaluated
Keywords :
associative processing; computational complexity; directed graphs; parallel algorithms; SIMD-type abstract model; STAR procedure; STAR-machine; associative parallel algorithm; correctness verification; critical cycle selection; directed weighted graphs; optimum branchings; time complexity; vertical data processing; Application software; Concurrent computing; Data processing; Electronic mail; Geophysics computing; Graph theory; Mathematics; Parallel algorithms; Polynomials; Tree graphs;
Conference_Titel :
Parallel and Distributed Systems, 2000. Proceedings. Seventh International Conference on
Conference_Location :
Iwate
Print_ISBN :
0-7695-0568-6
DOI :
10.1109/ICPADS.2000.857729
