基于压入与重标记可提前终止的最大流最小割求解算法

发布者：技术转移办公室发布时间：2025-04-14浏览次数：60

技术主题：后摩尔器件与集成系统

发明名称：基于压入与重标记可提前终止的最大流最小割求解算法

申请时间：2022-08-11

申请号：US17798898

摘要：提供了一种用于早期终止push‑Relebel算法的max-flow//min-cut解算法。 所述max-flow//min-cut求解算法用于不需要精确最大流量的应用，包括：通过分离条件和稳定条件定义Push-Relebel算法的提前终止条件； 在所述Push-Relebel算法的运行过程中，若任意时刻所述集合T中不存在源节点s，s∈S，则确定满足所述分离条件； 若所述集合T中不存在活动节点，则确定满足所述稳定条件； 以及如果所述分离条件和所述稳定性条件都满足，则终止所述推送-重新贝尔算法。 提早的终止技术是为了大大减少冗余计算，并确保算法在所有情况下都能正确终止。