An algorithm for packing non-zero \(A\)-paths in group-labelled graphs (Q949790): Difference between revisions

Let \(G=(V,E)\) be an oriented graph whose edges are labelled by the elements of a group \(\Gamma\) and let \(A\subseteq 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\). An efficient algorithm is given 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.