New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
Theory of Computing, Volume 17(5), pp. 1-27, 2021
Bibliography with links to cited articles
[1] Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams: Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th FOCS, pp. 59–78. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.14]
[2] Amir Abboud, Karl Bringmann, Holger Dell, and Jesper Nederlof: More consequences of falsifying SETH and the orthogonal vectors conjecture. In Proc. 50th STOC, pp. 253–266. ACM Press, 2018. [doi:10.1145/3188745.3188938]
[3] Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemysław Uznański, and Daniel Wolleb-Graf: Faster algorithms for all-pairs bounded min-cuts. In Proc. 46th Internat. Colloq. on Automata, Languages, and Programming (ICALP’19), volume 132, pp. 7:1–7:15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ICALP.2019.7]
[4] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: New algorithms and lower bounds for all-pairs max-flow in undirected graphs. In Proc. 31st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’20), pp. 48–61. SIAM, 2020. [doi:10.1137/1.9781611975994.4, arXiv:1901.01412]
[5] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: APMF ¡ APSP? Gomory–Hu tree for unweighted graphs in almost-quadratic time, 2021. Accepted to FOCS 2021. [arXiv:2106.02981]
[6] Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi: Subcubic algorithms for Gomory–Hu tree in unweighted graphs. In Proc. 53rd STOC, pp. 1725–1737. ACM Press, 2021. [doi:10.1145/3406325.3451073]
[7] Amir Abboud and Virginia Vassilevska Williams: Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th FOCS, pp. 434–443. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.53]
[8] Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu: Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098–1122, 2018. Preliminary version in STOC’15. [doi:doi:10.1137/15M1050987]
[9] Eyad Alkassar, Sascha Böhme, Kurt Mehlhorn, and Christine Rizkallah: A framework for the verification of certifying computations. J. Autom. Reason., 52(3):241–273, 2014. Preliminary version in CAV’11. [doi:10.1007/s10817-013-9289-2]
[10] Nima Anari and Vijay V. Vazirani: Planar graph perfect matching is in NC. J. ACM, 67(4):21:1–21:34, 2020. Preliminary version in FOCS’18. [doi:10.1145/3397504]
[11] Srinivasa Rao Arikati, Shiva Chaudhuri, and Christos D. Zaroliagis: All-pairs min-cut in sparse networks. J. Algorithms, 29(1):82–110, 1998. [doi:10.1006/jagm.1998.0961]
[12] Jørgen Bang-Jensen, András Frank, and Bill Jackson: Preserving and increasing local edge-connectivity in mixed graphs. SIAM J. Discr. Math., 8(2):155–178, 1995. [doi:10.1137/S0036142993226983]
[13] Anand Bhalgat, Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi: An (mn) Gomory–Hu tree construction algorithm for unweighted graphs. In Proc. 39th STOC, pp. 605–614. ACM Press, 2007. [doi:10.1145/1250790.1250879]
[14] Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen: All-pairs minimum cuts in near-linear time for surface-embedded graphs. In Proc. 32nd Internat. Symp. Comput. Geom. (SoCG’16), pp. 22:1–22:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.SoCG.2016.22, arXiv:1411.7055]
[15] Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang: Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances. In Proc. 53rd STOC, pp. 859–869. ACM Press, 2021. [doi:10.1145/3406325.3451108]
[16] Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proc. 7th Innovations in Theoret. Comp. Sci. conf. (ITCS’16), pp. 261–270. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.1145/2840728.2840746]
[17] Ho Yee Cheung, Lap Chi Lau, and Kai Man Leung: Graph connectivities, network coding, and expander graphs. SIAM J. Comput., 42(3):733–751, 2013. [doi:10.1137/110844970]
[18] Robert T. Chien: Synthesis of a communication net. IBM J. Res. Dev., 4(3):311–320, 1960. [doi:10.1147/rd.43.0311]
[19] Richard Cole and Ramesh Hariharan: A fast algorithm for computing Steiner edge connectivity. In Proc. 35th STOC, pp. 167–176. ACM Press, 2003. [doi:10.1145/780542.780568]
[20] Jack Edmonds: Submodular functions, matroids, and certain polyhedra. In Combinatorial Structures and Their Appl., Proc. Conf. Calgary 1969, pp. 69–87. Gordon and Breach, 1970. [doi:10.1007/3-540-36478-1_2]
[21] Lester R. Ford and Delbert R. Fulkerson: Maximal flow through a network. Canad. J. Math., 8(3):399–404, 1956. [doi:10.4153/CJM-1956-045-5]
[22] Harold N. Gabow: A matroid approach to finding edge connectivity and packing arborescences. J. Comput. System Sci., 50(2):259–273, 1995. Preliminary version in STOC’91. [doi:10.1006/jcss.1995.1022]
[23] Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams: Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(2):1–35, 2019. Preliminary version in SODA’17. [doi:10.1145/3196275]
[24] Loukas Georgiadis, Daniel Graf, Giuseppe F. Italiano, Nikos Parotsidis, and Przemysław Uznański: All-pairs 2-reachability in O(nω log n) time. In Proc. 44th Internat. Colloq. on Automata, Languages, and Programming (ICALP’17), volume 80, pp. 74:1–74:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ICALP.2017.74]
[25] Andrew V. Goldberg and Kostas Tsioutsiouliklis: Cut tree algorithms: an experimental study. J. Algorithms, 38(1):51–83, 2001. [doi:10.1006/jagm.2000.1136]
[26] Ralph E. Gomory and Te Chiang Hu: Multi-terminal network flows. J. SIAM, 9(4):551–570, 1961. [doi:10.1137/0109047]
[27] Frieda Granot and Refael Hassin: Multi-terminal maximum flows in node-capacitated networks. Discr. Appl. Math., 13(2-3):157–163, 1986. [doi:10.1016/0166-218X(86)90079-X]
[28] Dan Gusfield: Very simple methods for all pairs network flow analysis. SIAM J. Comput., 19(1):143–155, 1990. [doi:10.1137/0219009]
[29] Ramesh Hariharan, Telikepalli Kavitha, and Debmalya Panigrahi: Efficient algorithms for computing all low s - t edge connectivities and related problems. In Proc. 18th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’07), pp. 127–136. SIAM, 2007. ACM DL.
[30] Refael Hassin and Asaf Levin: Flow trees for vertex-capacitated networks. Discr. Appl. Math., 155(4):572–578, 2007. [doi:10.1016/j.dam.2006.08.012]
[31] Russell Impagliazzo and Ramamohan Paturi: On the complexity of k-SAT. J. Comput. System Sci., 62(2):367–375, 2001. [doi:10.1006/jcss.2000.1727]
[32] Frederick Jelinek: On the maximum number of different entries in the terminal capacity matrix of oriented communication nets. IRE Trans. Circuit Theory, 10(2):307–308, 1963. [doi:10.1109/TCT.1963.1082149]
[33] Robert Krauthgamer and Ohad Trabelsi: Conditional lower bounds for all-pairs max-flow. ACM Trans. Algorithms, 14(4):42:1–42:15, 2018. [doi:10.1145/3212510]
[34] Marvin Künnemann: On nondeterministic derandomization of Freivalds’ algorithm: Consequences, avenues and algorithmic progress. In Proc. 26th Eur. Symp. Algorithms (ESA’18), pp. 56:1–56:16. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ESA.2018.56]
[35] Jakub Lacki, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen: Single source – all sinks max flows in planar digraphs. In Proc. 53rd FOCS, pp. 599–608. IEEE Comp. Soc., 2012. [doi:10.1109/FOCS.2012.66]
[36] Yin Tat Lee and Aaron Sidford: Path finding methods for linear programming: Solving linear programs in () iterations and faster algorithms for maximum flow. In Proc. 55th FOCS, pp. 424–433. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.52]
[37] Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak: A nearly optimal all-pairs min-cuts algorithm in simple graphs, 2021. Accepted to FOCS 2021. [arXiv:2106.02233]
[38] Yang P. Liu and Aaron Sidford: Faster energy maximization for faster maximum flow. In Proc. 52nd STOC, pp. 803–814. ACM Press, 2020. [doi:10.1145/3357713.3384247]
[39] Aleksander Madry: Computing maximum flow with augmenting electrical flows. In Proc. 57th FOCS, pp. 593–602. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.70]
[40] Wataru Mayeda: Terminal and branch capacity matrices of a communication net. IRE Trans. Circuit Theory, 7(3):261–269, 1960. [doi:10.1109/TCT.1960.1086673]
[41] Wataru Mayeda: On oriented communication nets. IRE Trans. Circuit Theory, 9(3):261–267, 1962. [doi:10.1109/TCT.1962.1086912]
[42] Ross M. McConnell, Kurt Mehlhorn, Stefan Näher, and Pascal Schweitzer: Certifying algorithms. Computer Sci. Review, 5(2):119–161, 2011. [doi:10.1016/j.cosrev.2010.09.009]
[43] Debmalya Panigrahi: Gomory–Hu trees. In Ming-Yang Kao, editor, Encyclopedia of Algorithms, pp. 858–861. Springer, 2016. [doi:10.1007/978-1-4939-2864-4_168]
[44] Aaron Sidford and Kevin Tian: Coordinate methods for accelerating ℓ∞ regression and faster approximate maximum flow. In Proc. 59th FOCS, pp. 922–933. IEEE Comp. Soc., 2018. [doi:10.1109/FOCS.2018.00091]
[45] R. Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2–3):357–365, 2005. [doi:10.1016/j.tcs.2005.09.023]
[46] R. Ryan Williams: Strong ETH breaks with Merlin and Arthur: Short non-interactive proofs of batch evaluation. In Proc. 31st Comput. Complexity Conf. (CCC’16), pp. 2:1–2:17. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016. [doi:10.4230/LIPIcs.CCC.2016.2, arXiv:1601.04743]
[47] Zhenyu Wu and Richard Leahy: An optimal graph theoretic approach to data clustering: Theory and its application to image segmentation. ACM Trans. Pattern Anal. Machine Intell., 15(11):1101–1113, 1993. [doi:10.1109/34.244673]
[48] Tianyi Zhang: Faster cut-equivalent trees in simple graphs, 2021. [arXiv:2106.03305]