二部グラフ辺彩色

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

二部グラフ辺彩色O(MlogM)これかな en.wikipedia.org/wiki/Edge_colo… 1. 魔法で正則にする 2. 次数が奇数なら完全マッチングを見つけて塗る（魔法を使うとほぼ線形らしい） 3. オイラー路を取って交互に振り分けて再帰的にやる かな？

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

正則にする魔法： 最大次数をkとする。 1. 次数k/2以下の頂点が複数あればマージする 2. 適当に頂点を追加して左右の頂点数を合わせる 3. 残りは適当に辺を追加して次数を合わせる（多重辺もokなら本当に適当で良さそう） このとき、辺の本数は高々2倍+kにしかならないので嬉しい。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

k-正則二部グラフの完全マッチングO(m log n)： ipsj.ixsq.nii.ac.jp/ej/?action=rep… まずk=2^tだとすると、オイラー路を取って奇数番目の辺だけを残すっていうのを繰り返せばO(m)で完全マッチングが見つかる（Gabowのアルゴリズム）

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

2^t-1<k<2^tの場合は、適当なダミー辺を追加して2^t正則にする。ここでダミー辺の割合は高々半分。 これに対してGabowをする（ただし奇数番目と偶数番目でダミー辺が多い方を捨てる） するとダミー辺がn/2以下の完全マッチングが見つかる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

元のグラフにこのマッチングを2^t-k個追加すると、今度はダミー辺が高々1/4になる。 これに対してGabowをするとダミー辺がn/4以下の完全マッチングが見つかって・・・というのをO(log n)回繰り返せばダミー辺が0の完全マッチングが見つかる。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

天才すぎんか？ （ちなみにまだ読んでないけどO(m+n log n log k)もできるらしい） O(m log n)のを使えば元の辺彩色は多分O(m log m log k)。

ꑄ꒖ꐇꌅꏂ🐾 @snuke_

O(m log n log k)