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

Автор C137, история, 5 лет назад, По-английски

Hello Codeforces

Recently I have written tutorial talking about the Maximum Independent Set Problem in Bipartite Graphs. I have tried all my best to cover this problem, and explained some related problems: Minimum Vertex Cover (MVC), Maximum Cardinality Bipartite Matching (MCBM) and Kőnig’s Theorem. You can find the Tutorial in my website.

I am new to blog writing, so any feedback (positive and negative one) will be highly appropriated.

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

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

It's worth mentioning that $$$V_L \cup V_R$$$ and $$$U_L \cup U_R$$$ actually form the minimum cut of the graph as per Ford-Fulkerson theorem.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +10 Проголосовать: не нравится

I am pretty sure that we can have a better bound for Dinic's algo when running it on the flow graph that solves MCBM. The time complexity would be similar to Hopcroft Karp's algo.

Also, Edmond Karp's algo's time complexity will definitely be better on such flow graphs. Think about it, there are at most $$$\frac{n}{2} + 1$$$ iterations of BFS.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    More than just similar complexity, Hopcroft-Karp is exactly Dinic's algorithm in a bipartite matching graph.

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

    When I mentioned the time complexity I meant the worse case in a general graph. I will clarify it, thanks for pointing it out.

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

      While a non-tight Big-O time complexity is technically correct due to definition of Big-O, I think it is nicer to give a tighter bound where possible.

      e.g. if we have a line graph as our flow graph, surely we can see that any augmenting path algo will terminate in one pass right?