Cycle Contraction in Oriented Graphs / Nalivaiko P.V. // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2010. ? 3. P. 36-38 [Moscow Univ. Math. Bulletin. Vol. 65, No 3, 2010. P. 116-118].

There exists an efficient algorithm for finding a branching of minimal weight among all branchings of maximal cardinality in an oriented graph. This algorithm is based on the cycle contraction technique and was developed by Tarjan. It is shown that this technique is applicable to a more general problem when the branching is subject to the additional condition that the set of vertices covered by this branching must be independent with respect to a given matroid.

Key words: graph, branching, matroid, cycle contraction.