Open AccessA Note on Parametric Network Flows
Author(s) -
Edward Minieka
Publication year - 1973
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.19.5.585
Subject(s) - flow network , mathematical proof , terminal (telecommunication) , mathematical optimization , minimum cost flow problem , maximum flow problem , flow (mathematics) , mathematics , computer science , parametric statistics , discrete mathematics , algorithm , telecommunications , statistics , geometry
In their paper [Doulliez, P. J., M. R. Rao. 1971. Maximal flow in a multi-terminal network with any one are subject to failure. Management Sci. 18 (1, September) 48-58.], Doulliez and Rao present algorithms that solve two flow problems for a single source, multi-terminal network. The first problem that they solve is the construction of a flow that maximizes the value of t, where the demand at each sink is a nondecreasing, linear function of t. Given such a flow, the second problem that they solve is the construction of a flow that maximizes the value of t when the capacity of an arc is reduced. This paper supplies a finiteness proof for the first algorithm and sketches a finiteness proof for the second algorithm. The proofs are based on the well-known fact that a network possesses only a finite number of different spanning trees.