Abstract:
An efficient algorithm exists for solution of the problem of determination of 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 in this paper 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.
Fulltext:
PDF file (338 kB)