A strongly polynomial algorithm is developed for finding an integer-valued feasible $st$-flow of given flow-amount which is decreasingly minimal on a specified subset $F$ of edges in the sense that the largest flow-value on $F$ is as small as possible, within this, the second largest flow-value on $F$ is as small as possible, within this, the third largest flow-value on $F$ is as small as possible, and so on. A characterization of the set of these $st$-flows gives rise to an algorithm to compute a cheapest $F$-decreasingly minimal integer-valued feasible $st$-flow of given flow-amount.
Bibtex entry:
@techreport{egres-19-09,
AUTHOR | = | {Frank, Andr{\'a}s and Murota, Kazuo}, |
TITLE | = | {Discrete Decreasing Minimization, Part III: Network Flows}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2019}, |
NUMBER | = | {TR-2019-09} |