Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .

  • $\begingroup$ There are some monographs on these topics. On network flow, there is Network Flows: Theory, Algorithms, and Applications. On matching, there's the classic Matching Theory by Lovász and Plummer. $\endgroup$ – Yuval Filmus Jan 16 '19 at 13:34

Based on the book "Algorithm Design" by Kleinberg and Tardos, Kevin Wayne has a set of slides (second part here) where the following applications of max flow and matching are presented in some detail:

  • survey design
  • airline scheduling
  • image segmentation
  • project selection
  • baseball elimination
  • assignment problem
  • input-queued switching

For even more examples, have a look into the exercises of Chapter 7 of Kleinberg and Tardos' book, or into the exercises of the book "Network Flows: Theory, Algorithms, and Applications" by Ahuja, Magnanti and Orlin.

  • $\begingroup$ thanks , exactly what i needed to see . $\endgroup$ – Mohbenay Jan 16 '19 at 16:07

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.