Блог пользователя AmericanPsycho

What are all topics and algorithms about flows?
Автор AmericanPsycho, история, 8 лет назад, По-английски

All I have read about flows is Edmonds Karp’s Algorithm, which works for maximum flow, but I have seen that there are better algorithms than this one, and there are different problems that maximum flow (like mincost, dinic and others), I would like a list of all the topics and algorithms that are useful for learning network flow!

Thanks in advance!

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

Just google ffs

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    why do you need to be rude? I don't think it is easy to google all these as the topic is really broad and not CP specific, so it would be nice if there is someone experienced that can summarize it as well.

    → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

To solve a network maximum flow problem you can use the Edmonds-Karp algorithm. It's a bit long, but it's easy to understand.

However, like you said, there are some variation that make Edmonds-Karp not neccessarily the best option.

I know there are a lot of algorithms that solve the max flow problem, but here is a list of the must used algorithms in competitive programming, and some useful topics:

  • Edmonds-Karp Algorithm (Solves the max-flow in O(VE2))

  • Dinic's Algorithm (Solves the max-flow in O(V2E))

  • Bipartite Matching, a special case of the matching problem, which can be solved applying Edmonds-Karp via DFS.

  • Hopcroft-Karp Algorithm, solves the bipartite matching problem with overall complexity

  • Max Flow — Min Cut Theorem

  • Min Cost Max Flow problem, can be solved using an Edmonds Karp variant, replacing the BFS with a fast Bellman-Ford implementation

  • The assignment problem (and Min Weight Bipartite Matching), can be solved using min cost max flow

  • The Hungarian Algorithm, solves the assignment problem with O(n3) complexity

  • Push-Relabel Algorithm

  • König's Theorem

  • Dilworth's Theorem

The last two theorems allows us to solve the Minimum Vertex Cover and Maximum Independent Set problems in bipartite graphs using flow algorithms

One of the most important things about these kind of problems is to find that it is indeed a network flow problem. That's why these topics require a lot of practice.

Personally, I find very hard to understand some algorithms like the Hungarian Method, so it is important to prepare a good library with these implementations. This way we avoid the struggle during contests!

Hope you find this list useful :)

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

I think the topics provided by snacache is enough comprehensive. I'm going to share some links which helped me while learning network flow.

  1. Go through the 4 max flow tutorials from Topcoder tutorials index

  2. Explanation of complexity of Edmonds-Karp (I personally had a tough time understanding the reasoning behind the complexity until I saw this answer. )

  3. Links for understanding Dinic:

  1. For mincost maxflow go through the 3 mincost maxflow tutorials given in the first link for topcoder tutorials

  2. Mincost Maxflow with SPFA (Shortest Path Faster Algorithm) achieves a better average case complexity than mincost maxflow with Bellman Ford. Learn SPFA from here

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    mind sharing insight like when to use dinic and when to use edmonds? Or is it solely on how dense the graph is?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

      I actually always use Dinic. Dinic's worst case complexity ( O( V^2 * E )) is better than that of Edmond Karp ( O( V * E^2 ) ). And I haven't heard that Edmond Karp works better in any special graph than Dinic.

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

I see others have described the algorithms and problems, I'd just add the link to an efficient implementation of Diniz's algorithm here. The page is in Russian (the English version of the page doesn't have Diniz's algorithm yet), Google Translate is your friend. Page also includes efficient implementations of other algorithms in C++.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Atcoder is having a lot of flow problems in ABCs these days. Can someone please share the list of flow problems if one has compiled.

→ Ответить