Abstract

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.

File

nepomnyashchaya.pdf6.18 MB

Pages

77-92