.png){kind=icon}
.png){kind=icon}
Return
Maximum flow acceleration by traversing tree based two-boundary graph contraction
.png){kind=icon}
PRE
AI
DOI：10.1016/j.eswa.2023.120151.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The maximum flow (max-flow) problem is so fundamental that the corresponding algorithms have many applications in many scenarios. A common acceleration strategy is to reduce graph size by contracting subgraphs, but there are few candidate subgraphs with no size limit that can guarantee exact max-flow solutions after contraction. We add a new subgraph contraction condition to the existing conditions with corresponding efficient locating algorithm, and we propose a max-flow acceleration algorithm using traversing tree-based contraction (TTCMax). TTCMax can work efficiently only by using connectivity information. Through depth-first traversing, it can contract two-boundary graphs of any size into edges, and then accelerate existing max-flow algorithms using contracted graphs. Large-scale random and real-world graph experiments test its effect and the acceleration ratio can be more than 50 times with low graph reduction overhead, indicating that the proposed algorithm can be used as an effective complement to existing algorithms.
Keywords:
Tree-cut mapping
Boundary node
Maximum flow
Graph contraction
Overlay
Journal
IF:
7.5
Papers:
2.9W
Citations:
10.2W