DocumentCode
2257948
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
fYear
2000
fDate
2000
Firstpage
455
Lastpage
462
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Parallel and Distributed Systems, 2000. Proceedings. Seventh International Conference on
Conference_Location
Iwate
ISSN
1521-9097
Print_ISBN
0-7695-0568-6
Type
conf
DOI
10.1109/ICPADS.2000.857729
Filename
857729
Link To Document