THE OPTIMAL PATH-MATCHING PROBLEM

We describe a common generalization of the weighted matching problem a nd the weighted matroid intersection problem. In this context we estab lish common generalizations of the main results on those two problems- polynomial-time solvability, min-max theorems, and totally dual integr al polyhedral descriptions. New applications of these results include a strongly polynomial separation algorithm for the convex hull of matc hable sets of a graph, and a polynomial-time algorithm to compute the rank of a certain matrix of indeterminates.