News for hackers. Stuff that matters.
Re:Solving the minimum cut problem for undirected graphs by ColinWright on Wednesday April 17, 2024 @05:27PM (#40070226)
Unless I'm missing something (which is entirely possible, I have a cold and might not be thinking straight) ...

Max-Flow runs on directed graphs. These are undirected graphs.

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.
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.
Re:Solving the minimum cut problem for undirected graphs by armanboyaci on Wednesday April 17, 2024 @08:21PM (#40071626)
You can compute the max-flow of an undirected graph. The edges have capacities and in the undirected case you assume that capacity can be used in both 'directions'.