TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration. (3rd July 2022)

• Record Type: Journal Article
• Authors: Wei, Wei; Mu, Yashuang; Yang, Weidong; Xu, Heyang
• Is Part Of: Optimization. Volume 71:Number 7(2022)
• Page Start: 2047
• Page End: 2072
• Publication Date: 2022-07-03
• Subjects: Boundary node -- maximum flow -- graph contraction -- overlay -- parallel algorithm; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1847110
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : The maximum-flow (max-flow) problem is a classic combinatorial optimization problem that has been used in many kinds of applications.The existing methods accelerate by contracting large-size subgraphs, but can only obtain approximated results with significant deviations. To address the problem, we propose a two-boundary graph pattern-based contraction algorithm for lossless max-flow acceleration (TBGMax). TBGMax can obtain accurate results by contracting two-boundary graphs of any size into edges, only involves connectivity information and does not need any extra information such as the edge capacity and local topology. TBGMax can accelerate even further by excluding irrelevant nodes. Random and real graphs-based simulations show that TBGMax can accelerate classic max-flow algorithm by up to 75.1 times in benchmark problem families and up to 22.3 times in real-world road networks, and at best only involve an average of 0.002% of the nodes in a graph.