Max-flow/min-cut solution algorithm for early terminating push-relabel algorithm
US12223691B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Sep 22, 2021 |
| Grant date | Feb 11, 2025 |
| Priority date | — |
| Expiry date | Sep 22, 2041 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06V10/96
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A max-flow/min-cut solution algorithm for early terminating a push-relabel algorithm is provided. The max-flow/min-cut solution algorithm is used for an application that does not require an exact maximum flow, and includes: defining an early termination condition of the push-relabel algorithm by a separation condition and a stable condition; determining that the separation condition is satisfied if there is no source node s, s∈S, in the set T at any time in an operation process of the push-relabel algorithm; determining that the stable condition is satisfied if there is no active node in the set T; and terminating the push-relabel algorithm if both the separation condition and the stability condition are satisfied. The early termination technique is proposed to greatly reduce redundant computations and ensure that the algorithm terminates correctly in all cases.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.