Let G = (V, E) be an oriented graph whose edges are labelled by the elements of a group Gamma and let A subset of V. An A-path is a path whose ends are both in A. The weight of a path P in G is the sum of the group values on forward oriented arcs minus the sum of the backward oriented arcs in P. (If Gamma is not abelian, we sum the labels in their order along the path.) We give an efficient algorithm for finding a maximum collection of vertex-disjoint A-paths each of non-zero weight. When A=V this problem is equivalent to the maximum matching problem.
展开▼
