Faster Algorithms for the Generalized Network Flow Problem

References

• Ahuja R. K., Magnanti T. L., Orlin J. B.Network Flows: Theory, Algorithms, and Applications (1993) (Prentice Hall, Englewood Cliffs, New Jersey) Google Scholar
• Cohen E., Megiddo N. New algorithms for generalized network flows. Math. Programming (1994) 64:325–336Crossref, Google Scholar
• Ford L. R., Fulkerson D. R.Flows in Networks (1962) (Princeton University Press, Princeton, New Jersey) Crossref, Google Scholar
• Fredman M. L., Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms. J. Assoc. Comput. Mach. (1987) 34:596–615Crossref, Google Scholar
• Glover F., Hultz J., Klingman D., Stutz J. Generalized networks: A fundamental computer-based planning tool. Management Sci. (1978) 24:12Link, Google Scholar
• Goldberg A. V., Tarjan R. E. Finding minimum-cost circulations by canceling negative cycles. J. Assoc. Comput. Mach. (1989) 36:388–397Crossref, Google Scholar
• Goldberg A. V., Plotkin S. A., Tardos É. Combinatorial algorithms for the generalized circulation problem. Math. Oper. Res. (1991) 16:351–381Link, Google Scholar
• Goldfarb D., Jin Z. A faster combinatorial algorithm for the generalized circulation problem. Math. Oper. Res. (1996) 21:529–539Link, Google Scholar
• Goldfarb D., Jin Z., Orlin J.Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem (1996) . Technical report, IEOR Department, Columbia University, New YorkGoogle Scholar
• Gondran M., Minoux M.Graphs and Algorithms (1984) (Wiley, New York) Google Scholar
• Kamath A., Palmon O. Improved interior point algorithms for exact and approximate solution of multicommodity flow problems. Proc. 6th Annual ACM-SIAM Sympos. Discrete Algorithms (1995) 502–511Google Scholar
• Kapoor S., Vaidya P. M. Fast algorithms for convex quadratic programming and multi-commodity flows. Proc. 18th Annual ACM Sympos. Theory Comput. (1986) 147–159Google Scholar
• Murray S. M.An interior point approach to the generalized flow problem with costs and related problems (1992) . Ph.D. thesis, Stanford UniversityGoogle Scholar
• Onaga K. Optimal flows in general communication networks. J. Franklin Inst. (1967) 283:308–327Crossref, Google Scholar
• Radzik T.Approximate generalized circulation (1993) . Technical report 93-2, Cornell Computational Optimization Project, Cornell UniversityGoogle Scholar
• Vaidya P. M. Speeding up linear programming using fast matrix multiplication. Proc. 30th IEEE Annual Sympos. Foundations of Comput. Sci. (1989) 332–337Crossref, Google Scholar
• Zadeh N. A bad network problem for the simplex method and other minimum cost flow algorithms. Math. Programming (1973) 5:255–266Crossref, Google Scholar