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

DOI10.1080/02331934.2020.1847110zbMath1495.90166OpenAlexW3111288692MaRDI QIDQ5090297

Weidong Yang, Wei Wei, Yashuang Mu, Heyang Xu

Publication date: 18 July 2022

Published in: Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/02331934.2020.1847110

zbMATH Keywords

parallel algorithmmaximum flowgraph contractionoverlayboundary node

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Simplifying maximum flow computations: the effect of shrinking and good initial flows
• An efficient algorithm for the minimum capacity cut problem
• A distributed mincut/maxflow algorithm combining path augmentation and push-relabel
• Maximal Flow Through a Network
• An O ( n log n ) algorithm for maximum st -flow in a directed planar graph
• Very Simple Methods for All Pairs Network Flow Analysis
• A new approach to the maximum-flow problem
• Multi-Terminal Network Flows
• An O(n2log n) parallel max-flow algorithm
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• Network Flow and Testing Graph Connectivity
• A new approach to the minimum cut problem
• On implementing push-relabel method for the maximum flow problem
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• Minimum cuts in near-linear time

This page was built for publication: TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration