ようこそ

最小有向全域木を求める | Chu-Liu/Edmonds' algorithm

これはなに

最小全域木問題の有向グラフバージョン。

無向グラフに対する最小全域木は、クラスカル法とかプリム法とかで求められるけど、有向グラフの場合はどうすればいいのか気になったので調べてみた。

Chu-Liu/Edmonds' algorithmというアルゴリズムで計算量は$O(nm)$。頑張ったら$O(m\log n)$や$O(m + n\log n)$とかにできるらしい。$O(m + n\log n)$のやつはフィボナッチヒープを使うとのこと。

この記事では$O(nm)$のアルゴリズムについてまとめる。

続きを読む

第6回 git challenge 参加記

「ブログに書くまでがgit challenge」とのことで、ブログを始めました!

git challengeとは

mixiさん主催の、gitに関する技術を競うコンテストです。 今回は第6回でした。

mixi-recruit.snar.jp

続きを読む