Efficient implementation of Edmonds' algorithm for finding optimum branchings on associative parallel processors
Anna Nepomniaschaya · 2002
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.