- 2012-04-10 (Tue) 13:50
- 一般
午前の輪講で transitive closure (TC) の計算量が頂点数 n に対して O(n^2) と見積もられていたのでなんか変だなぁと思ってググってたら，http://www.cs.hut.fi/~enu/thesis.html にある論文の 2.3.3 節に「TC と行列乗算は同じ計算量」とかいう定理が紹介されていた（定理自体は1970にFurman が発表）．そこから適当に調べるとその定理の証明を書いてそうなのが http://rjlipton.files.wordpress.com/2009/10/matrix1971.pdf にあって，行列乗算でTCは自然に計算できて，逆向きは A* = 1 + A + A^2 + ... = 1/(1-A) の関係を使うっぽい（まあ，こちらも自然か…… あれ？ 逆行列なら分かるが掛け算？ よーわからん）．
TC を計算する別の手法としては強連結成分分解ベースのものがあるらしいのだけど，ぶっちゃけ沢山あるのでよくわからん．やっぱり Warshall のが一番わかりやすくていいね．
- Newer: ことはじめ