Optimum matching forests I: Special weights

We introduce the concept of matching forests as a generalization of branchings in a directed graph and matchings in an undirected graph. Given special weights on the edges of a mixed graph, we present an efficient algorithm for finding an optimum weight-sum matching forest. The algorithm is a careful application of known branching and matching algorithms. The maximum cardinality matching forest problem is solved as a special case.Research partially supported by a N.R.C. of Canada Postdoctorate Fellowship.