Analysis of Complex Networks

15.4 Conclusion

The mathematical models for finding optimal flows in dynamic networks represent the extension and generalization of the classical optimal flow problems on static networks. Such dynamic models can be used for studying and solving a large class of practical problems as well as problems from the theory of graphs and combinatorics. The mathematical apparatus for determining optimal solutions of the network flow problems based on the time expanded network method has been elaborated and grounded. New efficient algorithms for finding minimum cost and maximum dynamic flows have been derived. The time-expanded network method has been specified for the multicommodity case of optimal dynamic flow problems, and algorithms for solving such problems have been developed.

References

1 Ahuja, R., Magnati, T., Orlin, J. Network flows. Prentice-Hall, Englewood Cliffs, 1993.

2 Aronson, J. A survey of dynamic network flows. Annals of Operations Research, 1989, 20, 1–66.

3 Assad, A. Multicommodity network flows: a survey. Networks, 1978, 8, 37–92.

4 Bland, R.G., Jensen, D.L. On the computational behavior of a polynomial-time network flow algorithm. Technical Report 661, School of Operations Research and Industrial Engineering, Cornell University, 1985.

5 McBride, R. Progress made in solving the multicommodity flow problems. SIAM Journal on Optimization, 1998, 8(4), 947–955.

6 Cai, X., Sha, D., Wong, C.K. Time-varying minimum cost flow problems. European Journal of Operational Research ...