Stoer-Wagner: a simple min-cut algorithm

[@wusswuzz5818]

Very nice explanation. Advent of Code 2023 day 25 brought me here.

[@rafaszepieniec6408]

thanks for making this video, I'd never understand this from the old, badly formatted presentation I got at my uni

[@Edigor100]

great explanation, thanks

[@yevgeniygrechka6431]

Thank you for this video. One part where I would suggest giving additional detail is at 10:50. It isn't very obvious why the edges corresponding to the second term are all in C_{s_{i+1}}. Of course the reason is because only one of the nodes connecting to u_s_{i+1} is an active node, so the rest of those edges must be in the same grouping as that active node, but that took a bit of thinking to figure out.

[@mogustew]

Thanks for the feedback, that's a good point. It's important to remember that we are inducting on the sequence of active vertices and so between any pair of active vertices u_{s_i} and u_{s_{i+1}}, all other added nodes in-between must have been in the part containing u_{s_i} and opposite the part containing u_{s_{i+1}}.

[@bedrichmazourek3289]

Thank you so much, this video was really helpful and of very high quality.. Also loved the haiku

[@mogustew]

Thanks for your complement (in the future videos I hope to speak more naturally ':)

[@danidorfman277]

Great explanation :)

[@mogustew]

Thanks!

[@Exp102]

The most monotone voice I've ever heard but actually a good content.

[@stephaniesews6603]

Great tutorial, but if you're a newbie, you're lost. Minute 4:00 bugged me especially, explaining the iteration again would not have hurt. However, I'm not a newbie and could follow along with pen and paper and I think I got Stoer-Wagner down now!

[@mogustew]

Thanks for your suggestion!