Title :
Efficient implementation of Edmonds´ algorithm for finding optimum branchings on associative parallel processors
Author :
Nepomniaschaya, A.S.
Author_Institution :
Inst. of Comput. Math. & Math. Geophys., Acad. of Sci., Novosibirsk, Russia
Abstract :
We propose an efficient parallel implementation of Edmonds´ (1967) algorithm for finding optimum branchings on a model of the SIMD type with vertical data processing (the STAR-machine). To this end for a directed graph given as a list of triples (edge vertices and the weight), we construct a new associative version of Edmonds´ algorithm. This version is represented as the corresponding STAR procedure whose correctness is proved. We show that on vertical processing systems Edmonds´ algorithm takes O(n log n) time, where n is the number of graph vertices
Keywords :
associative processing; directed graphs; parallel algorithms; parallel machines; SIMD; STAR-machine; associative parallel processors; directed graph; graph vertices; optimum branchings; parallel algorithm; vertical data processing; Associative processing; Concurrent computing; Data processing; Data structures; Electronic mail; Geophysics computing; Graph theory; Mathematics; Polynomials; Tree graphs;
Conference_Titel :
Parallel and Distributed Systems, 2001. ICPADS 2001. Proceedings. Eighth International Conference on
Conference_Location :
Kyongju City
Print_ISBN :
0-7695-1153-8
DOI :
10.1109/ICPADS.2001.934794
