Vi anser att problemet med att hitta den minsta kapacitetsnedskärningen i ett riktat nätverk G med n noder. Detta problem har tillämpningar för nätverkstillförlitlighet och överlevnadsförmåga och är användbart i subrutiner för andra nätoptimeringsproblem. Man kan använda ett maximalt flödesproblem för att hitta en minsta skärning som separerar en angiven källa nod s från en angiven diskbänk nod t, och genom att variera diskbänk noden kan man hitta en minsta skärning i G som en sekvens av högst 2n - 2 maximala flödesproblem. Vi visar sedan hur man kan minska drifttiden för dessa 2n -2 maximala flödesalgoritmer till drifttiden för att lösa ett enda maximalt flödesproblem. Den resulterande körtiden är O(nm log(n 2 /m)) för att hitta den minsta nedskärningen i antingen ett riktat eller ett oriktat nätverk.
Hao och Orlin REF visade vidare den minsta skärningen i en riktad graf kan reduceras till en enda flödesberäkning.
A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
{'venue': 'JOURNAL OF ALGORITHMS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}