GabowのEdmonds' Algorithm(一般マッチング O(VElogV))の解説と実装 - Qiita

これは「データ構造とアルゴリズム Advent Calendar 2018」14日目の記事です． この記事は, Gabowの論文をもとに書かせていただいています. こっちを読むと完全に理解できます. マッチング? けんちょんさんの記事から画像をお借りしました. マッチングは辺の集合であって, どの2辺も両端を共有しないようなものをマッチングといいます. その集合の中で, 一番辺の数が多いものを最大マッチングといいいます. 二部マッチング? こちらもけんちょんさんの記事 二部グラフ(グラフの頂点が２グループに分かれていて, グラフの辺がその２グループをまたぐものしか無いグラフ)での二部マッチングは最大フローに帰着して解くことが出来ます. 導入 二部マッチングの問題は最大フローで解けたりしますが, 一般マッチングはそうはいきません. また実装が難しいこと(Edmonds' Blossom De