Home > 一般 > transitive closure の計算

transitive closure の計算

  • 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 のが一番わかりやすくていいね.

★下記に2つの英単語をスペースで区切って入力してください

Home > 一般 > transitive closure の計算

Search
Feeds

Page Top