Greedy concepts for network flow problems (Q1088884)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Greedy concepts for network flow problems |
scientific article |
Statements
Greedy concepts for network flow problems (English)
0 references
1986
0 references
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.
0 references
cost optimal flow
0 references
series-parallel networks
0 references
greedy algorithm
0 references
augmenting path method
0 references
series composition
0 references
parallel composition
0 references
tree structures
0 references
polymatroidal
0 references