Randomized Parallel Algorithms for Matroid Union and Intersection, with Applications to Arborescences and Edge-Disjoint Spanning Trees
Hariharan Narayanan, Huzur Saran, Vijay V. Vazirani · SIAM Journal on Computing · 1994
The strong link between matroids and matching is used to extend the ideas that resulted in the design of random $NC(RNC)$ algorithms for matching to obtain $RNC$ algorithms for the matroid union, intersection, and matching problems, and for linearly representable matroids. As a consequence, $RNC$ algorithms for the well-known problems of finding an arboresence and a maximum cardinality set of edge-disjoint spanning trees in a graph are obtained. The key tools used are linear algebra and randomization.