首页>
外国专利>
REGION BASED PUSH-RELABEL ALGORITHM FOR EFFICIENT COMPUTATION OF MAXIMUM FLOW
REGION BASED PUSH-RELABEL ALGORITHM FOR EFFICIENT COMPUTATION OF MAXIMUM FLOW
展开▼
机译:有效计算最大流量的基于区域的推相关算法
展开▼
页面导航
摘要
著录项
相似文献
摘要
A region-based push-relabel formulation is disclosed that removes the requirement that the entire graph should fit into the computer memory and yields an implementation that can reduce the required size and redundancy of accesses to the data memory, thus improving speed performance, while allowing for an efficient parallel processing implementation. The algorithm assigns all vertices that are not part of the sources or sinks with a value of 1. Sinks are assigned with zeros and sources are assigned a label equal to the number of their vertices. The preflow is then pushed from the sources to their neighbors, if any. When the preflow has all reached the boundaries, an adjacent region of the neighboring set is selected and preflow is pushed within this region. When the values of the preflow have been exhausted, region relabeling is done to update the label values. This is repeated within the region until all preflow has exited to the boundary of this region. The operation is then repeated for the neighboring regions that now contain the preflow. Regions which have no preflow may be skipped, thereby realizing a savings in processing resources.
展开▼