Re:Solving the minimum cut problem for undirected graphs
by eutectic on Wednesday April 17, 2024 @06:42PM
(#40070854)
Also, the problem is to find a global min-cut, which requires all-pairs max flow.
[ Parent
| on HN ]
Re:Solving the minimum cut problem for undirected graphs
by gloria_mundi on Wednesday April 17, 2024 @08:54PM
(#40071853)
Not actually all-pairs max flow, you can fix the source and consider all possible sinks. In the AoC problem we also know that the min-cut is 3, so we can abort the flow algorithm as soon as we have found a 4-flow.