[1] Abraham, I. and Neiman, O.. Using petal-decompositions to build a low stretch spanning tree. In Proceedings of the 44th Annual ACM Symposium on the Theory of Computing, pages 395–406, 2012. Full version available at https://www.cs.bgu.ac.il/~neimano/spanning-full1.pdf. Accessed May 14, 2018.CrossRefGoogle Scholar

[2] Ahlswede, R. and Winter, A.. Strong converse for identification via quantum channels. IEEE Transactions on Information Theory, 48:569–579, 2002.Google Scholar

[3] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B.. Network flows. In Nemhauser, G. L., Rinnooy Kan, A. H. G., and Todd, M. J., editors, Optimization, volume 1 of Handbooks in Operations Research and Management Science, pages 211–369. North-Holland, Amsterdam, The Netherlands, 1989.CrossRefGoogle Scholar

[4] Ahuja, R. K., Magnanti, T. L., and Orlin, J. B.. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, Englewood Cliffs, NJ, USA, 1993.Google Scholar

[5] Ahuja, R. K. and Orlin, J. B.. A fast and simple algorithm for the maximum flow problem. Operations Research, 37:748–759, 1989.Google Scholar

[6] Ahuja, R. K. and Orlin, J. B.. Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems. Naval Research Logistics, 38:413–430, 1991.3.0.CO;2-J>CrossRefGoogle Scholar

[7] Ahuja, R. K., Orlin, J. B., and Tarjan, R. E.. Improved time bounds for the maximum flow problem. SIAM Journal on Computing, 18:939–954, 1989.Google Scholar

[8] Alon, N., Karp, R. M., Peleg, D., and West, D.. A graph-theoretical game and its application to the k-server problem. SIAM Journal on Computing, 24:78–100, 1995.Google Scholar

[9] Anderson, R. J. and Setubal, J.. Goldberg’s algorithm for maximum flow in perspective: A computational study. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1–18. American Mathematical Society, Providence, RI, USA, 1993.Google Scholar

[10] Arora, S., Hazan, E., and Kale, S.. The multiplicative weights update method: A meta-algorithm and applications. Theory of Computing, 8:121–164, 2012.Google Scholar

[11] Aspvall, B. I.. Efficient Algorithms for Certain Satisfiability and Linear Programming Problems. PhD thesis, Department of Computer Science, Stanford University, August 1980. Also appears as Technical Report STAN-CS-80-822.Google Scholar

[12] Awerbuch, B. and Leighton, T.. A simple local-control approximation algorithm for multicommodity flow. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 459–468, 1993.Google Scholar

[13] Awerbuch, B. and Leighton, T.. Improved approximation algorithms for the multicommodity flow problem and local competitive routing in dynamic networks. In Proceedings of the 26th Annual ACM Symposium on the Theory of Computing, pages 487–496, 1994.Google Scholar

[14] Baier, G., Köhler, E., and Skutella, M.. The k-splittable flow problem. Algorithmica, 42:231–248, 2005.CrossRefGoogle Scholar

[15] Barahona, F. and Tardos, É.. Note on Weintraub’s minimum-cost circulation algorithm. SIAM Journal on Computing, 18:579–583, 1989.CrossRefGoogle Scholar

[16] Batson, J., Spielman, D. A., and Srivastava, N.. Twice-Ramanujan sparsifiers. SIAM Journal on Computing, 41:1704–1721, 2012.Google Scholar

[17] Batson, J., Spielman, D. A., and Srivastava, N.. Twice-Ramanujan sparsifiers. SIAM Review, 56:315–334, 2014.Google Scholar

[18] Bellman, R.. On a routing problem. Quarterly of Applied Mathematics, 16:87–90, 1958.CrossRefGoogle Scholar

[19] Benczúr, A. A. and Goemans, M. X.. Deformable polygon representation and near-mincuts. In Grötschel, M. and Katona, G. O. H., editors, Building Bridges, number 19 in Boylai Society Mathematical Studies, pages 103–135. Springer, Berlin, Germany, 2008.Google Scholar

[20] Benczúr, A. A. and Karger, D. R.. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM Journal on Computing, 44:290–319, 2015.Google Scholar

[21] Bertsekas, D. P. and Tseng, P.. Relaxation methods for minimum cost ordinary and generalized network flow problems. Operations Research, 36:93–114, 1988.Google Scholar

[22] Bertsekas, D. P. and Tseng, P.. RELAX-IV: A faster version of the RELAX code for solving minimum cost flow problems. Technical Report LIDS-P-2276, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, November 1994.Google Scholar

[23] Bhalgat, A., Hariharan, R., Kavitha, T., and Panigrahi, D.. An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs. In Proceedings of the 39th Annual ACM Symposium on the Theory of Computing, pages 605–614, 2007.Google Scholar

[24] Bienstock, D.. Potential Function Methods for Approximately Solving Linear Programming Problems: Theory and Practice. Kluwer Academic Publishers, New York, NY, USA, 2002.Google Scholar

[25] Bland, R. G. and Jensen, D. L.. On the computational behavior of a polynomial-time network flow algorithm. Mathematical Programming, 54:1–39, 1992.Google Scholar

[26] Bollobás, B.. Modern Graph Theory. Springer, New York, NY, USA, 1998.Google Scholar

[27] Boman, E. G., Deweese, K., and Gilbert, J. R.. Evaluating the potential of a dual randomized Kaczmarz Laplacian linear solver. Informatica, 40:95–107, 2016.Google Scholar

[28] Boykov, Y. and Kolmogorov, V.. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:1124–1137, 2004.CrossRefGoogle ScholarPubMed

[29] Bünnagel, U., Korte, B., and Vygen, J.. Efficient implementation of the Goldberg-Tarjan minimum-cost flow algorithm. Optimization Methods and Software, 10:157–174, 1998.Google Scholar

[30] Busacker, R. G. and Saaty, T. L.. Finite Graphs and Networks: An Introduction with Applications. McGraw-Hill Book Company, New York, NY, USA, 1965.Google Scholar

[31] Chandran, B. G. and Hochbaum, D. S.. A computational study of the pseudoflow and push-relabel algorithms for the maximum flow problem. Operations Research, 57:358–376, 2009.Google Scholar

[32] Chekuri, C. S., Goldberg, A. V., Karger, D. R., Levine, M. S., and Stein, C.. Experimental study of minimum cut algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 324–333, 1997.Google Scholar

[33] Cheng, C. K. and Hu, T. C.. Ancestor tree for arbitrary multi-terminal cut functions. Annals of Operations Research, 33:199–213, 1991.Google Scholar

[34] Cheriyan, J. and Maheshwari, S. N.. Analysis of preflow push algorithms for maximum network flow. SIAM Journal on Computing, 18:1057–1086, 1989.CrossRefGoogle Scholar

[35] Cheriyan, J. and Mehlhorn, K.. An analysis of the highest-level selection rule in the preflow-push max-flow algorithm. Information Processing Letters, 69:239–242, 1999.CrossRefGoogle Scholar

[36] Cherkasskii, B. V.. A fast algorithm for constructing a maximum flow through a network. American Mathematical Society Translations, 158:23–30, 1994.Google Scholar

[37] Cherkassky, B. V. and Goldberg, A. V.. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19:390–410, 1997.CrossRefGoogle Scholar

[38] Cherkassky, B. V. and Goldberg, A. V.. Negative-cycle detection algorithms. Mathematical Programming, 85:277–311, 1999.Google Scholar

[39] Cheung, T.-Y.. Computational comparison of eight methods for the maximum flow problem. ACM Transactions on Mathematical Software, 6:1–16, 1980.Google Scholar

[40] Christiano, P., Kelner, J. A., Mądry, A., Spielman, D., and Teng, S.-H.. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proceedings of the 43rd Annual ACM Symposium on the Theory of Computing, pages 273–282, 2011. Full version available at https://people.csail.mit.edu/madry/docs/maxflow.pdf. Accessed May 15, 2018.Google Scholar

[41] Cohen, E. and Megiddo, N.. New algorithms for generalized network flows. Mathematical Programming, 64:325–336, 1994.Google Scholar

[42] Cohen, M. B., Kyng, R., Miller, G. L., Pachocki, J. W., Peng, R., Rao, A. B., and Xu, S. C.. Solving SDD linear systems in nearly m log^1/2 n time. In Proceedings of the 46th Annual ACM Symposium on the Theory of Computing, pages 343–352, 2014.Google Scholar

[43] Cohen, M. B., Mądry, A., Sankowski, P., and A. Vladu, . Negative-weight shortest paths and unit capacity minimum cost flow in Õ(m^10/7 log W) time. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 752–771, 2017. Full version available at https://arxiv.org/pdf/1605.01717.pdf. Accessed June 8, 2018.Google Scholar

[44] Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., and Schrijver, A.. Combinatorial Optimization. John Wiley & Sons, New York, NY, USA, 1998.Google Scholar

[45] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C.. Introduction to Algorithms. MIT Press, Cambridge, MA, USA, third edition, 2009.Google Scholar

[46] Daitch, S. I. and Spielman, D. A.. Faster approximate lossy generalized flow via interior-point algorithms. In Proceedings of the 40th Annual ACM Symposium on the Theory of Computing, pages 451–460, 2008. Full version available at https://arxiv.org/pdf/0803.0988.pdf. Accessed February 3, 2019.Google Scholar

[47] Dantzig, G. B.. Application of the simplex method to a transportation problem. In Koopmans, T. C., editor, Activity Analysis of Production and Allocation, number 13 in Cowles Commission for Research in Economics, pages 359–373. John Wiley & Sons, New York, NY, USA, 1951.Google Scholar

[48] Dantzig, G. B.. Linear Programming and Extensions. Princeton University Press, Princeton, NJ, USA, 1963.Google Scholar

[49] Dantzig, G. B. and Fulkerson, D. R.. On the max-flow min-cut theorem of networks. In Kuhn, H. W. and Tucker, A. W., editors, Linear Inequalities and Related Systems, number 38 in Annals of Mathematics Studies, pages 215–222. Princeton University Press, Princeton, NJ, USA, 1956.Google Scholar

[50] Derigs, U. and Meier, W.. Implementing Goldberg’s max-flow-algorithm – A computational investigation. ZOR – Methods and Models of Operations Research, 33:383–403, 1989.Google Scholar

[51] Dijkstra, E. W.. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269–271, 1959.CrossRefGoogle Scholar

[52] Dinic, E. A.. An algorithm for the solution of the max-flow problem with power estimation. Doklady Akademii Nauk SSSR, 194:754–757, 1970. In Russian. English version in Soviet Mathematics Doklady 11:1277–1280, 1970.Google Scholar

[53] Dinitz, E. A., Karzanov, A. V., and Lomonosov, M. V.. O strukture sistemy minimal’nykh rebernykh razrezov grafa. In Fridman, A. A., editor, Issledovaniya po Diskretnoĭ Optimizatsii, pages 290–306. Nauka, Moscow, 1976. In Russian. English translation available at http://alexander-karzanov.net/ScannedOld/76_cactus_transl.pdf. Accessed February 14, 2018.Google Scholar

[54] Dinitz, Y.. Dinitz’ algorithm: The original version and Even’s version. In Goldreich, O., Rosenberg, A. L., and Selman, A. L., editors, Theoretical Computer Science: Essays in Memory of Shimon Even, number 3895 in Lecture Notes in Computer Science, pages 218–240. Springer, Berlin, Germany, 2006.Google Scholar

[55] Doyle, P. G. and Snell, J. L.. Random Walks and Electric Networks. The Mathematical Association of America, Washington DC, USA, 1984. Online version available at https://arxiv.org/pdf/math/0001057.pdf. Accessed January 24, 2019.Google Scholar

[56] Dubhashi, D. P. and Panconesi, A.. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 2009.Google Scholar

[57] Edmonds, J. and Karp, R. M.. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19:248–264, 1972.Google Scholar

[58] Elias, P., Feinstein, A., and Shannon, C. E.. A note on the maximum flow through a network. IRE Transactions on Information Theory, 2:117–119, 1956.Google Scholar

[59] Even, S. and Tarjan, R. E.. Network flow and testing graph connectivity. SIAM Journal on Computing, 4:507–518, 1975.Google Scholar

[60] Fleischer, L.. Building chain and cactus representations of all minimum cuts from Hao-Orlin in the same asymptotic run time. Journal of Algorithms, 33:51–72, 1999.CrossRefGoogle Scholar

[61] Fleischer, L. K.. Approximating fractional multicommodity flow independent of the number of commodities. SIAM Journal on Discrete Mathematics, 13:505–520, 2000.Google Scholar

[62] Ford, L. R. Jr. Network flow theory. Paper P-923, The RAND Corporation, Santa Monica, CA, USA, 1956.Google Scholar

[63] Ford, L. R. Jr. and Fulkerson, D. R.. Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404, 1956.Google Scholar

[64] Ford, L. R. Jr. and Fulkerson, D. R.. Constructing maximal dynamic flows from static flows. Operations Research, 6:419–433, 1958.Google Scholar

[65] Ford, L. R. Jr. and Fulkerson, D. R.. A suggested computation for maximal multicommodity network flows. Management Science, 5:97–101, 1958.Google Scholar

[66] Ford, L. R. Jr. and Fulkerson, D. R.. Flows in Networks. Princeton University Press, Princeton, NJ, USA, 1962.Google Scholar

[67] Foster, R. M.. The average impedance of an electrical network. In Reissner Anniversary Volume: Contributions to Applied Mechanics, pages 333–340. J. W. Edwards, Ann Arbor, MI, USA, 1949.Google Scholar

[68] Frank, A.. Connectivity and network flows. In Graham, R. L., Grötschel, M., and Lovász, L., editors, Handbook of Combinatorics, volume I, pages 111–178. Elsevier B.V., Amsterdam, The Netherlands, 1995.Google Scholar

[69] Frank, A.. On the edge-connectivity algorithm of Nagamochi and Ibaraki. EGRES Quick Proof 2009-01, Department of Operations Research, Eötvös University, Budapest, Hungary, 2009. Available at http://www.cs.elte.hu/egres/qp/egresqp-09-01.pdf. Accessed September 11, 2012.Google Scholar

[70] Fredman, M. L., Sedgewick, R., Sleator, D. D., and Tarjan, R. E.. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1:111–129, 1986.CrossRefGoogle Scholar

[71] Fredman, M. L. and Tarjan, R. E.. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34:596–615, 1987.Google Scholar

[72] Fujishige, S.. Another simple proof of the validity of Nagamochi and Ibaraki’s min-cut algorithm and Queyranne’s extension to symmetric submodular function minimization. Journal of the Operations Research Society of Japan, 41:626–628, 1998.CrossRefGoogle Scholar

[73] Fujishige, S.. A maximum flow algorithm using MA ordering. Operations Research Letters, 31:176–178, 2003.CrossRefGoogle Scholar

[74] Fulkerson, D. R.. An out-of-kilter method for minimal-cost flow problems. SIAM Journal on Applied Mathematics, 9:18–27, 1961.Google Scholar

[75] Fulkerson, D. R. and Dantzig, G. B.. Computation of maximal flows in networks. Naval Research Logistics Quarterly, 2:277–283, 1955.Google Scholar

[76] Gabow, H. N.. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50:259–273, 1995.Google Scholar

[77] Gabow, H. N.. The minset-poset approach to representations of graph connectivity. ACM Transactions on Algorithms, 12, 2016. Article 24.CrossRefGoogle Scholar

[78] Gallo, G., Grigoriadis, M. D., and Tarjan, R. E.. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18:30–55, 1989.Google Scholar

[79] Garg, N. and Könemann, J.. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM Journal on Computing, 37:630–652, 2007.Google Scholar

[80] Glover, F. and Klingman, D.. On the equivalence of some generalized network problems to pure network problems. Mathematical Programming, 4:269–278, 1973.CrossRefGoogle Scholar

[81] Glover, F., Klingman, D., Mote, J., and Whitman, D.. Comprehensive computer evaluation and enhancement of maximum flow algorithms. Research Report 356, Center for Cybernetic Studies, University of Texas, Austin, October 1979. Available at http://www.dtic.mil/dtic/tr/fulltext/u2/a081941.pdf. Accessed May 29, 2018.Google Scholar

[82] Glover, F., Klingman, D., Mote, J., and Whitman, D.. An extended abstract of an indepth algorithmic and computational study for maximum flow problems. Discrete Applied Mathematics, 2:251–254, 1980.Google Scholar

[83] Goldberg, A. V.. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, EECS Department, University of California, Berkeley, 1984. Available at http://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/CSD-84-171.pdf. Accessed May 29, 2018.Google Scholar

[84] Goldberg, A. V.. An efficient implementation of a scaling minimum-cost flow algorithm. Journal of Algorithms, 22:1–29, 1997.Google Scholar

[85] Goldberg, A. V.. Two-level push-relabel algorithm for the maximum flow problem. In Goldberg, A. V. and Zhou, Y., editors, Algorithmic Aspects in Information and Management, number 5564 in Lecture Notes in Computer Science, pages 212–225. Springer, Berlin, Germany, 2009.CrossRefGoogle Scholar

[86] Goldberg, A. V., Hed, S., Kaplan, H., Kohli, P., Tarjan, R. E., and Werneck, R. F.. Faster and more dynamic maximum flow by incremental breadth-first search. In Bansal, N. and Finocchi, I., editors, Algorithms – ESA 2015, number 9294 in Lecture Notes in Computer Science, pages 619–630. Springer, Berlin, Germany, 2015.Google Scholar

[87] Goldberg, A. V. and Kharitonov, M.. On implementing scaling push-relabel algorithms for the minimum-cost flow problem. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1–18. American Mathematical Society, Providence, RI, USA, 1993.Google Scholar

[88] Goldberg, A. V., Oldham, J. D., Plotkin, S., and Stein, C.. An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity flow. In Bixby, R. E., Boyd, E. A., and Ríos-Mercado, R. Z., editors, Integer Programming and Combinatorial Optimization, 6th International IPCO Conference, volume 1412 of Lecture Notes in Computer Science, pages 338–352. Springer, Berlin, Germany, 1998.Google Scholar

[89] Goldberg, A. V., Plotkin, S. A., and Tardos, É.. Combinatorial algorithms for the generalized circulation problem. Mathematics of Operations Research, 16:351–381, 1991.CrossRefGoogle Scholar

[90] Goldberg, A. V. and Rao, S.. Beyond the flow decomposition barrier. Journal of the ACM, 45:783–797, 1998.Google Scholar

[91] Goldberg, A. V., Tardos, É., and Tarjan, R. E.. Network flow algorithms. In Korte, B., Lovaśz, L., Prömel, H. J., and Schrijver, A., editors, Paths, Flows, and VLSI-Layout, pages 101–164. Springer, Berlin, Germany, 1990.Google Scholar

[92] Goldberg, A. V. and Tarjan, R. E.. A new approach to the maximum-flow problem. Journal of the ACM, 35:921–940, 1988.CrossRefGoogle Scholar

[93] Goldberg, A. V. and Tarjan, R. E.. Finding minimum-cost circulations by canceling negative cycles. Journal of the ACM, 36:873–886, 1989.Google Scholar

[94] Goldberg, A. V. and Tarjan, R. E.. Finding minimum-cost circulations by successive approximation. Mathematics of Operations Research, 15:430–466, 1990.Google Scholar

[95] Goldberg, A. V. and Tarjan, R. E.. Efficient maximum flow algorithms. Communications of the ACM, 57:82–89, 2014.CrossRefGoogle Scholar

[96] Goldberg, A. V. and Tsioutsiouliklis, K.. Cut tree algorithms: An experimental study. Journal of Algorithms, 83:51–83, 2001.Google Scholar

[97] Goldfarb, D. and Hao, J.. Polynomial-time primal simplex algorithms for the minimum cost network flow problem. Algorithmica, 8:145–160, 1992.CrossRefGoogle Scholar

[98] Goldfarb, D. and Jin, Z.. A faster combinatorial algorithm for the generalized circulation problem. Mathematics of Operations Research, 21:529–539, 1996.CrossRefGoogle Scholar

[99] Goldfarb, D., Jin, Z., and Lin, Y.. A polynomial dual simplex algorithm for the generalized circulation problem. Mathematical Programming, 91:271–288, 2002.Google Scholar

[100] Goldfarb, D., Jin, Z., and Orlin, J. B.. Polynomial-time highest-gain augmenting path algorithms for the generalized circulation problem. Mathematics of Operations Research, 22:793–802, 1997.Google Scholar

[101] Gomory, R. E. and Hu, T. C.. Multi-terminal network flows. SIAM Journal on Applied Mathematics, 9:551–570, 1961.Google Scholar

[102] Grigoriadis, M. D. and Khachiyan, L. G.. Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM Journal on Optimization, 4:86–107, 1994.CrossRefGoogle Scholar

[103] Gusfield, D.. Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19:143–155, 1990.CrossRefGoogle Scholar

[104] Hao, J. and Orlin, J. B.. A faster algorithm for finding a minimum cut in a directed graph. Journal of Algorithms, 17:424–446, 1994.Google Scholar

[105] Harvey, N.. Lecture Notes from CPSC 536N: Randomized Algorithms, Winter 2012, Lectures 13 and 14. Available at http://www.cs.ubc.ca/~nickhar/W12/. Accessed May 14, 2018.Google Scholar

[106] Henzinger, M., Rao, S., and Wang, D.. Local flow partitioning for faster edge connectivity. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1919–1938, 2017.Google Scholar

[107] Hochbaum, D. S.. The pseudoflow algorithm: A new algorithm for the maximum flow problem. Operations Research, 56:992–1009, 2008.Google Scholar

[108] Hoffman, A. J.. Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Bellman, R. and Hall, M., Jr., editors, Combinatorial Analysis, volume X of Proceedings of Symposia in Applied Mathematics, pages 113–127, American Mathematical Society, Providence, RI, USA, 1960.CrossRefGoogle Scholar

[109] Hoffman, A. J.. On greedy algorithms that succeed. In Anderson, I., editor, Surveys in combinatorics 1985: Invited papers for the Tenth British Combinatorial Conference, number 103 in London Mathematical Society Lecture Note Series, pages 97–112. Cambridge University Press, Cambridge, UK, 1985.Google Scholar

[110] Hoffman, A. J.. On simple combinatorial optimization problems. Discrete Mathematics, 106/107:285–289, 1992.Google Scholar

[111] Hoppe, B. and Tardos, É.. The quickest transshipment problem. Mathematics of Operations Research, 25:36–62, 2000.Google Scholar

[112] Hoske, D., Lukarski, D., Meyerhenke, H., and Wegner, M.. Engineering a combinatorial Laplacian solver: Lessons learned. Algorithms, 9, 2016. Article 72.Google Scholar

[113] Hu, T. C.. Multi-commodity network flows. Operations Research, 11:344–360, 1963.Google Scholar

[114] IBM ILOG. CPLEX. https://www.ibm.com/analytics/cplex-optimizer.Google Scholar

[115] Imai, H.. On the practical efficiency of various maximum flow algorithms. Journal of the Operations Research Society of Japan, 26:61–82, 1983.CrossRefGoogle Scholar

[116] Jewell, W. S.. Optimal flow through networks with gains. Operations Research, 10:476–499, 1962.CrossRefGoogle Scholar

[117] Johnson, D. B.. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24:1–13, 1977.CrossRefGoogle Scholar

[118] Joshi, A., Goldstein, A. S., and Vaidya, P. M.. A fast implementation of a path-following algorithm for maximizing a linear function over a network polytope. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 267–298. American Mathematical Society, Providence, RI, USA, 1993.CrossRefGoogle Scholar

[119] Jünger, M., Rinaldi, G., and Thienel, S.. Practical performance of efficient minimum cut algorithms. Algorithmica, 26:172–195, 2000.Google Scholar

[120] Kamath, A. and Palmon, O.. Improved interior point algorithms for exact and approximation solution of multicommodity flow problems. In Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 502–511, 1995.Google Scholar

[121] Karger, D. and Plotkin, S.. Adding multiple cost constraints to combinatorial optimization problems, with applications to multicommodity flows. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, pages 18–25, 1995.Google Scholar

[122] Karger, D. R.. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24:383–413, 1999.CrossRefGoogle Scholar

[123] Karger, D. R.. Minimum cuts in near-linear time. Journal of the ACM, 47:46–76, 2000.Google Scholar

[124] Karger, D. R. and Panigrahi, D.. A near-linear time algorithm for constructing a cactus representation of minimum cuts. In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 246–255, 2009.Google Scholar

[125] Karger, D. R. and Stein, C.. A new approach to the minimum cut problem. Journal of the ACM, 43:601–640, 1996.CrossRefGoogle Scholar

[126] Karp, R. M.. A characterization of the minimum cycle mean in a digraph. Discrete Mathematics, 23:309–311, 1978.Google Scholar

[127] Karzanov, A. V.. O nakhozhdenii maksimal’nogo potoka v setyakh spetsial’nogo vida i nekotorykh prilozheniyakh. In Lyusternik, L. A., editor, Matematicheskie Voprosy Upravleniya Proizvodstvom, volume 5, pages 81–94. Moscow State University Press, Moscow, Russia, 1973. In Russian. English translation available at http://alexander-karzanov.net/ScannedOld/73_spec-net-flow_transl.pdf. Accessed February 3, 2019.Google Scholar

[128] Karzanov, A. V.. Determining the maximal flow in a network by the method of preflows. Soviet Mathematical Dokladi, 15:434–437, 1974.Google Scholar

[129] Karzanov, A. V. and Timofeev, E. A.. Efficient algorithm for finding all minimal edge cuts of a nonoriented graph. Cybernetics, 22:156–162, 1986.Google Scholar

[130] Kawarabayashi, K. and Thorup, M.. Deterministic global minimum cut of a simple graph in near-linear time. In Proceedings of the 47th Annual ACM Symposium on the Theory of Computing, pages 665–674, 2015.Google Scholar

[131] Kelner, J. A., Orecchia, L., Sidford, A., and Zhu, Z. A.. A simple combinatorial algorithm for solving SDD systems in nearly-linear time. In Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pages 911–920, 2013. Full version available at https://arxiv.org/pdf/1301.6628.pdf. Accessed May 14, 2018.Google Scholar

[132] Klein, M.. A primal method for minimal cost flows with applications to the assignment and transportation problems. Management Science, 14:205–220, 1967.CrossRefGoogle Scholar

[133] Klein, P., Plotkin, S., Stein, C., and Tardos, É.. Faster approximation algorithms for the unit capacity concurrent flow problems with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23:466–487, 1994.Google Scholar

[134] Kleinberg, J. and Tardos, É.. Algorithm Design. Addison Wesley, Boston, MA, USA, 2006.Google Scholar

[135] Korte, B. and Vygen, J.. Combinatorial Optimization: Theory and Algorithms. Springer, Berlin, Germany, Fifth edition, 2012.Google Scholar

[136] Kovács, P.. Minimum-cost flow algorithms: an experimental evaluation. Optimization Methods and Software, 30:94–127, 2015.Google Scholar

[137] Langston, M. A.. Fixed-parameter tractability, a prehistory. In Bodlaender, H. L., Downey, R., Formin, F. V., and Marx, D., editors, The Multivariate Algorithmic Revolution and Beyond – Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday, number 7370 in Lecture Notes in Computer Science, pages 3–16. Springer, Berlin, Germany, 2012.Google Scholar

[138] Larkin, D. H., Sen, S., and Tarjan, R. E.. A back-to-basics empirical study of priority queues. In Proceedings of the 16th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 61–72, 2014.Google Scholar

[139] Lawler, E. L.. Optimal cycles in doubly weighted directed linear graphs. In Rosenstiehl, P., editor, Theory of Graphs, International Symposium, pages 209– 213. Gordon and Breach, New York, NY, USA, 1967.Google Scholar

[140] Lee, Y. T. and Sidford, A.. Path-finding methods for linear programming: Solving linear programs in iterations and faster algorithms for maximum flow. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science, pages 424–433, 2014. Full versions available at https://arxiv.org/pdf/1312.6677.pdf and https://arxiv.org/pdf/1312.6713.pdf. Accessed June 8, 2018.Google Scholar

[141] Lee, Y. T. and Sun, H.. An SDP-based algorithm for linear-sized spectral sparsification. In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing, pages 678–687, 2017. Full version available at https://arxiv.org/pdf/1702.08415.pdf. Accessed May 14, 2018.Google Scholar

[142] Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, É., and Tragoudas, S.. Fast approximation algorithms for multicommodity flow problems. Journal of Computer and System Sciences, 50:228–243, 1995.Google Scholar

[143] Leong, T., Shor, P., and Stein, C.. Implementation of a combinatorial multicommodity flow algorithm. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 387–405. American Mathematical Society, Providence, RI, USA, 1993.Google Scholar

[144] Levine, M. S.. Experimental study of minimum cut algorithms. Master’s thesis, Massachusetts Institute of Technology, May 1997. Available as MIT LCS Technical Report TR-719, from http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-719.pdf. Accessed February 12, 2018.Google Scholar

[145] Löbel, A.. Solving large-scale real-world minimum-cost flow problems by a network simplex method. Technical Report SC 96-7, ZIB, 1996. Available at https://opus4.kobv.de/opus4-zib/frontdoor/index/index/docId/218. Accessed June 5, 2018.Google Scholar

[146] Mądry, A.. Computing maximum flow with augmenting electrical flows. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, pages 593–602, 2016. Full version available at https://people.csail.mit.edu/madry/docs/aug_flow.pdf. Accessed June 8, 2018.Google Scholar

[147] Mehlhorn, K.. Blocking flow algorithms for maximum network flow, Course notes, Summer 1999. Available at www.mpi-inf.mpg.de/~mehlhorn/ftp/Goldberg-Rao.ps. Accessed September 27, 2012.Google Scholar

[148] Mitzenmacher, M. and Upfal, E.. Probability and Computing. Cambridge University Press, Cambridge, UK, second edition, 2017.Google Scholar

[149] Moore, E. F.. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285–292, Harvard University Press, Cambridge, MA, USA, 1959.Google Scholar

[150] Motwani, R. and Raghavan, P.. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995.CrossRefGoogle Scholar

[151] Nagamochi, H. and Ibaraki, T.. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5:54–66, 1992.CrossRefGoogle Scholar

[152] Nagamochi, H., Ono, T., and Ibaraki, T.. Implementing an efficient minimum capacity cut algorithm. Mathematical Programming, 67:325–341, 1994.Google Scholar

[153] Nguyen, Q. C. and Venkateswaran, V.. Implementations of the Goldberg-Tarjan maximum flow algorithm. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 1–18. American Mathematical Society, Providence, RI, USA, 1993.Google Scholar

[154] Okamura, H. and Seymour, P. D.. Multicommodity flows in planar graphs. Journal of Combinatorial Theory B, 31:75–81, 1981.Google Scholar

[155] Olver, N. and Végh, L. A.. A simpler and faster strongly polynomial algorithm for generalized flow maximization. In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing, pages 100–111, 2017. Full version available at https://arxiv.org/pdf/1611.01778.pdf. Accessed July 30, 2018.Google Scholar

[156] Onaga, K.. Optimum flows in general communications networks. Journal of the Franklin Institute, 283:308–327, 1967.Google Scholar

[157] Orlin, J. B.. A faster strongly polynomial minimum cost flow algorithm. Operations Research, 41:338–350, 1993.CrossRefGoogle Scholar

[158] Orlin, J. B.. A polynomial time primal network simplex algorithm for minimum cost flows. Mathematical Programming, 78:109–129, 1997.CrossRefGoogle Scholar

[159] Orlin, J. B.. Max flows in O(mn) time, or better. In Proceedings of the 45th Annual ACM Symposium on the Theory of Computing, pages 765–774, 2013. Full version available at https://dspace.mit.edu/openaccess-disseminate/1721.1/88020. Accessed May 25, 2018.Google Scholar

[160] Padberg, M. and Rinaldi, G.. An efficient algorithm for the minimum cut problem. Mathematical Programming, 47:19–36, 1990.Google Scholar

[161] Papp, P. A.. Low-stretch spanning trees. BSc thesis, Eötvös Lorand University, May 2014. Available at http://web.cs.elte.hu/blobs/diplomamunkak/bsc_alkmat/2014/papp_pal_andras.pdf. Accessed May 14, 2018.Google Scholar

[162] Peng, R.. Approximate undirected maximum flows in O(mpolylog(n)) time. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1862–1867, 2016. Full version available at https://arxiv.org/pdf/1411.7631.pdf. Accessed May 15, 2018.Google Scholar

[163] Picard, J.-C. and Queyranne, M.. On the structure of all minimum cuts in a network and applications. Mathematical Programming Study, 13:8–16, 1980.CrossRefGoogle Scholar

[164] Plotkin, S. A., Shmoys, D. B., and Tardos, É.. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, 20:257–301, 1995.CrossRefGoogle Scholar

[165] Podderyugin, B. D.. Algorithm for determining the edge connectivity of a graph. In Voprosy Kibernetiki – Trudy Seminara po Kombinatornoĭ Mathematike, pages 136–141. Akademiya Nauk SSSR Nauchnyĭ Sovet po Kompleksnoĭ Probleme “Kibernetika”, Moscow, USSR, 1973. In Russian.Google Scholar

[166] Portugal, L. F., Resende, M. G. C., Veiga, G., and Júdice, J. J.. A truncated primal-infeasible dual-feasible network interior point method. Networks, 35:91–108, 2000.Google Scholar

[167] Queyranne, M.. Minimizing symmetric submodular functions. Mathematical Programming, 82:3–12, 1998.Google Scholar

[168] Radzik, T.. Fast deterministic approximation for the multicommodity flow problem. Mathematical Programming, 78:43–58, 1997.Google Scholar

[169] Radzik, T.. Faster algorithms for the generalized network flow problem. Mathematics of Operations Research, 23:69–100, 1998.Google Scholar

[170] Radzik, T.. Improving time bounds on maximum generalised flow computations by contracting the network. Theoretical Computer Science, 312:75–97, 2004.Google Scholar

[171] Radzik, T. and Yang, S.. Experimental evaluation of algorithmic solutions for the maximum generalised flow problem. Technical Report TR-01-09, Department of Computer Science, King’s College London, 2001.Google Scholar

[172] Resende, M. G. and Veiga, G.. An efficient implementation of a network interior point method. In Johnson, D. S. and McGeoch, C. C., editors, Network Flows and Matching, First DIMACS Implementation Challenge, number 12 in DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 299–348. American Mathematical Society, Providence, RI, USA, 1993.Google Scholar

[173] Restrepo, M. and Williamson, D. P.. A simple GAP-canceling algorithm for the generalized maximum flow problem. Mathematical Programming, Series A, 118:47–74, 2009.Google Scholar

[174] Robinson, J.. A note on the Hitchcock-Koopmans problem. Research Memorandum RM-407, RAND Corporation, June 1950.Google Scholar

[175] Röck, H.. Scaling techniques for minimal cost network flows. In Pape, U., editor, Discrete Structures and Algorithms, Proceedings of the Workshop WG 79, pages 181–192. Carl Hanser Verlag, München, Germany, 1980.Google Scholar

[176] Schrijver, A.. On the history of the transportation and maximum flow problems. Mathematical Programming, Series B, 91:437–445, 2002.CrossRefGoogle Scholar

[177] Schrijver, A.. Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin, Germany, 2003.Google Scholar

[178] Schwartz, B. L.. Possible winners in partially completed tournaments. SIAM Review, 8:302–308, 1966.Google Scholar

[179] Seymour, P. D.. A short proof of the two-commodity flow theorem. Journal of Combinatorial Theory B, 26:370–371, 1979.CrossRefGoogle Scholar

[180] Shahrokhi, F. and Matula, D. W.. The maximum concurrent flow problem. Journal of the ACM, 37:318–334, 1990.CrossRefGoogle Scholar

[181] Skutella, M.. An introduction to network flows over time. In Cook, W. J., Lovász, L., and Vygen, J., editors, Research Trends in Combinatorial Optimization. Springer, Berlin, Germany, 2009.Google Scholar

[182] Sleator, D. D. and Tarjan, R. E.. A data structure for dynamic trees. Journal of Computer and System Sciences, 26:362–391, 1983.Google Scholar

[183] Sokkalingam, P. T., Ahuja, R. K., and Orlin, J. B.. New polynomial-time cycle-canceling algorithms for minimum-cost flows. Networks, 36:53–63, 2000.3.0.CO;2-Y>CrossRefGoogle Scholar

[184] Spielman, D. A. and Srivastava, N.. Graph sparsification by effective resistances. SIAM Journal on Computing, 40:1913–1926, 2011.Google Scholar

[185] Spielman, D. A. and Teng, S.-H.. Spectral sparsification of graphs. SIAM Journal on Computing, 40:981–1025, 2011.CrossRefGoogle Scholar

[186] Spielman, D. A. and Teng, S.-H.. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM Journal on Matrix Analysis and Applications, 35:835–885, 2014.Google Scholar

[187] Stoer, M. and Wagner, F.. A simple min-cut algorithm. Journal of the ACM, 44:585–591, 1997.CrossRefGoogle Scholar

[188] Tardos, É.. A strongly polynomial minimum cost circulation algorithm. Combinatorica, 5:247–255, 1985.Google Scholar

[189] Tardos, É.. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34:250–256, 1986.Google Scholar

[190] Tardos, É. and Wayne, K. D.. Simple generalized maximum flow algorithms. In Bixby, R. E., Boyd, E. A., and Ríos-Mercado, R. Z., editors, Integer Programming and Combinatorial Optimization, number 1412 in Lecture Notes in Computer Science, pages 310–324, Springer, Berlin, Germany, 1998.CrossRefGoogle Scholar

[191] Tarjan, R. E.. Shortest paths. Technical report, AT&T Bell Laboratories, Murray Hill, NJ, USA, 1981.Google Scholar

[192] Tarjan, R. E.. Data Structures and Network Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1983.CrossRefGoogle Scholar

[193] Tarjan, R. E.. Efficiency of the primal network simplex algorithm for the minimum-cost circulation problem. Mathematics of Operations Research, 14:272–291, 1991.Google Scholar

[194] Tomizawa, N.. On some techniques useful for solution of transportation network problems. Networks, 1:173–194, 1971.Google Scholar

[195] Tropp, J. A.. User-friendly tail bounds for sums of random matrics. Foundations of Computational Mathematics, 12:389–434, 2012.CrossRefGoogle Scholar

[196] Tropp, J. A.. An introduction to matrix concentration inequalities. Foundations and Trends in Machine Learning, 8(1–2):1–230, 2015. Also available at https://arxiv.org/pdf/1501.01571.pdf. Accessed May 15, 2018.Google Scholar

[197] Truemper, K.. An efficient scaling procedure for gain networks. Networks, 6:151–159, 1976.CrossRefGoogle Scholar

[198] Truemper, K.. On max flows with gains and pure min-cost flows. SIAM Journal on Applied Mathematics, 32:450–456, 1977.Google Scholar

[199] Vaidya, P. M.. Speeding-up linear programming using fast matrix multiplication. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 332–337, 1989.Google Scholar

[200] Végh, L. A.. A strongly polynomial algorithm for generalized flow maximization. Mathematics of Operations Research, 42:117–211, 2017.Google Scholar

[201] Wallacher, C.. A generalization of the minimum-mean cycle selection rule in cycle canceling algorithms. Technical report, Abteilung für Optimierung, Institut für Angewandte Mathematik, Technische Universität Carolo-Wilhelmina, Braunschweig, Germany, 1991.Google Scholar

[202] Wayne, K. D.. Generalized Maximum Flow Algorithms. PhD thesis, Cornell University, January 1999.Google Scholar

[203] Wayne, K. D.. A new property and a faster algorithm for baseball elimination. SIAM Journal on Discrete Mathematics, 14:223–229, 2001.Google Scholar

[204] Wayne, K. D.. A polynomial combinatorial algorithm for generalized minimum cost flow. Mathematics of Operations Research, 27:445–459, 2002.CrossRefGoogle Scholar

[205] Weintraub, A.. A primal algorithm to solve network flow problems with convex costs. Management Science, 21:87–97, 1974.Google Scholar

[206] Williamson, D. P. and Shmoys, D. B.. The Design of Approximation Algorithms. Cambridge University Press, New York, NY, USA, 2011.Google Scholar