An associative version of Edmond's algorithm for finding optimum branchings

In this paper we propose a representation of Edmonds' algorithm for finding optimum branchings on an abstract 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 associative algorithms for finding a critical cycle (or a cycle of the maximal weight), for contracting a critical cycle and for expanding the nested critical cycles. We obtain that on vertical processing systems Edmonds' algorithm takes O(n log n) time, where n is the number of graph vertices.