I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may find Network Flow useful. I want to refrain from using standard problems like Baseball problem, marriage problem, edge disjoint. I need Ideas for such problem which needs to be represented as a graph and then using Network flow we can find the solution.

  • $\begingroup$ How about min cut? $\endgroup$ – Yuval Filmus Apr 4 '17 at 19:02
  • 1
    $\begingroup$ what about image segmentation or matrix rounding? $\endgroup$ – abc Apr 4 '17 at 19:26
  • $\begingroup$ @YuvalFilmus min cut is also very standard, I want to add something new. $\endgroup$ – rishabh Apr 5 '17 at 8:10

Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing. For instance, it has been used for image segmentation, image stitching, seam carving, image denoising, stereo image correspondence, and more.

See, e.g., https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision, What's the relationship of max-flow-min-cut and Markov Random Fields?, https://cs.stackexchange.com/a/37423/755, https://en.wikipedia.org/wiki/Image_segmentation#Graph_partitioning_methods

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.