Partitioning the edge set of a bipartite graph into chain packings: Complexity of some variations (Q1399253): Difference between revisions

The author extends the decomposition theorem of Birkhoff-von Neumann for nonnegative matrices with constant row and column sums to integral matrices whose entries can be positive or negative. In graph-theoretical interpretation, instead of matchings we have collections of oriented paths with disjoint end nodes.