TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration

References

• Boykov Y, Kolmogorov V. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. IEEE Trans Pattern Anal Mach Intell. 2004; 26: 1124–1137.
   PubMed Web of Science ®Google Scholar
• Goldberg AV, Tarjan RE. Efficient maximum flow algorithms. Comm. ACM. 2014;57:82–89.
   Web of Science ®Google Scholar
• Verma T, Dhruv B. MaxFlow revisited: an empirical comparison of maxflow algorithms for dense vision problems. Proc. British Machine Vision Conference; 2012. p. 1–12.
   Google Scholar
• Zhang YP, Hua B, Jiang J, et al. Research on the maximum flow in large-scale network. Proc. Int. Conf. Computational Intelligence and Security; 2011. p. 482–486.
   Google Scholar
• Zhang Y, Xu X, Hua B, et al. Contracting community for computing maximum flow. Proc. Int. Conf. Granular Computing; 2012. p. 651–656.
   Google Scholar
• Zhao S, Xu X, Hua B, et al. Contraction network for solving maximum flow problem. Proc. ACM SIGKDD Workshop on Mining Data Semantics; 2012. p. 1–6.
   Google Scholar
• Ford LR, Fulkerson DR. Maximal flow through a network. Canad J Math. 1956;8:399–404.
   Google Scholar
• Edmonds J, Karp RM. Theoretical improvements in algorithmic efficiency for network flow problems. J ACM. 1972;19:248–264.
   Web of Science ®Google Scholar
• Goldberg AV, Tarjan RE. A new approach to the maximum flow problem. J ACM. 1988;35:921–940.
   Web of Science ®Google Scholar
• Even S, Tarjan RE. Network flow and testing graph connectivity. SIAM J Comput. 1975;4:507–518.
   Google Scholar
• Borradaile G, Klein PN. An O(n log n) algorithm for maximum st-flow in a directed planar graph. J ACM. 2009;56:1–30.
   Web of Science ®Google Scholar
• Christiano P, Kelner J, Madry A. Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs. Proc. ACM Symposium on Theory of Computing; 2010. p. 1–9.
   Google Scholar
• Kelner A, Lee YT. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. Proc. ACMSIAM Symposium on Discrete Algorithms; 2014. p. 217–226.
   Google Scholar
• Sherman J. Nearly maximum flows in nearly linear time. Proc. IEEE Symposium on Foundations of Computer Science; 2013. p. 263–269.
   Google Scholar
• Anderson R, Setubal JC. A parallel implementation of the push-relabel algorithm for the maximum flow problem. J Parallel Distrib Comput. 1995;1:17–26.
   Google Scholar
• Shiloach Y, Vishkin U. An O(n2log n) parallel max-flow algorithm. J Algo. 1982;2:128–146.
   Google Scholar
• Gomory RE, Hu TC. Multi-terminal network flows. J Soc Indust Appl Math. 1961;9:551–570.
   Google Scholar
• Gusfield D. Very simple methods for all pairs network flow analysis. SIAM J Comput. 1990;19:143–155.
   Web of Science ®Google Scholar
• Scheuermann B, Rosenhahn B. Slimcuts: Graphcuts for high resolution images using graph reduction. Proc. Int. Workshop on energy minimization methods in computer vision and pattern recognition; 2011. p. 219–232.
   Google Scholar
• Liers F, Pardella G. Simplifying maximum flow computations: the effect of shrinking and good initial flows. Discrete Appl Math. 2011; 159: 2187–2203.
   Web of Science ®Google Scholar
• Zhao S, Su J, Liu Q, et al. To solve maximum flow problem of network with a layering method. J Comput Res Develop. 2014;51:1845–1853.
   Google Scholar
• Wei W, Liu Y, Zhang R. SPLMax: exploiting the simple path introduced locality for maximum flow acceleration. IEEE Comm Lett. 2018;22:1330–1333.
   Web of Science ®Google Scholar
• Hopcroft J, Tarjan R. Algorithm 447: efficient algorithms for graph manipulation. Comm ACM. 1973;16:372–378.
   Web of Science ®Google Scholar
• Goldberg AV. Homepage of Andrew Goldberg's network optimization library; 2006. Available from: http://www.avglab.com/andrew/soft.html
   Google Scholar
• Hochbaum DS. Homepage of Hochbaum's pseudo-flow implementation. 2009. Available from: https://riot.ieor.berkeley.edu/Applications/Pseudoflow/maxflow.html
   Google Scholar
• Shekhovtsov A. Homepage of a distributed algorithm for mincut/maxflow combining path augmentation and push-relabel; 2019. Available from: http://cmp.felk.cvut.cz/shekhovt/d_maxflow/index.html
   Google Scholar
• Shekhovtsov A, Hlavac V. A distributed mincut/maxflow algorithm combining path augmentation and push-Relabel. Int J Comput Vis. 2013;104:315–342.
   Web of Science ®Google Scholar
• Wikipedia. Homepage of Edmonds–Karp algorithm in Wikipedia; 2019. Available from: https://en.wikipedia.org/wiki/Edmonds-Karp_algorithm
   Google Scholar
• IBM Corporation. Homepage of CPLEX optimizer. 2019. Available from: https://www.ibm.com/analytics/cplex-optimizer
   Google Scholar
• David SJ, Catherine CM. Network flows and matching: first DIMACS implementation challenge. AMS; 1993.
   Google Scholar
• Naher S. Homepage of typical generators for max-flow problems; 2003. Available from: http://www.informatik.uni-trier.de/naeher/Professur/research/generators/maxflow/
   Google Scholar
• Cherkassy BV, Goldberg AV. On implementing push-relabel method for the maximum flow problem. Proc. Int. Conf. Integer Programming and Combinatorial Optimization; 1995. p. 157–171.
   Google Scholar
• Schultes D. United States road networks (TIGER/Line); 2019. Available from: http://www.dis.uniroma1.it/challenge9/data/tiger/
   Google Scholar
• Karger DR. Minimum cuts in near-linear time. J ACM. 2000;47:46–76.
   Web of Science ®Google Scholar
• Karger DR, Stein C. A new approach to the minimum cut problem. J ACM. 1996;43:601–640.
   Web of Science ®Google Scholar
• Karzanov AV. Determining the maximal flow in a network by the method of preflows. Soviet Math Dokladi. 1974;15:434–437.
   Google Scholar
• Padberg M, Rinaldi G. An efficient algorithm for the minimum capacity cut problem. Math Program. 1990;47:19–36.
   Web of Science ®Google Scholar