Greedy concepts for network flow problems (Q1088884): Difference between revisions

The problem of finding a cost optimal flow in series-parallel networks can be solved by the greedy algorithm which in this case is identical to the augmenting path method. In this paper the same result is derived by demonstrating that series composition and parallel composition preserves the property that the problem can be solved by the greedy algorithm. This leads to an algorithm which is different from the augmenting path method. Applications of these concepts to tree structures are discussed and it is shown that these structures are polymatroidal in contrast to the series- parallel case.