https://twitter.com/kinaba のログ (twilog の方が便利です。)
| 岡嶋二人の『おかしな二人』よんでた。面白かった。密度の濃い本だった。主要作品がどう生まれたかアイデア段階から片っ端から書き起こしながら、このコンビがどう生まれてどう消えたかまで全部書いてあるのだから当然といえば当然なのだけど、にしてもすごい | |
| @eomole http://www.dis.uniroma1.it/~demetres/docs/jacm-tc.pdf これ使うと何かできそうなのでえおもるさん読んで僕に解説して | |
| 見ずに投げたけど普通に計算量にωが出現していた。これは見るからに現実には使えなさそう系だ | |
| http://dl.acm.org/citation.cfm?doid=1059513.1059514 Trade-offs for fully dynamic transitive closure on DAGs: breaking through the O(n^2 barrier 読んだ。意外とめっちゃシンプルだった。(続 | |
| 続) 推移閉包を行列で保持するとして、edge一本の追加はその両端の隣接ベクトルの縦×横の掛け算を足し込むことなので、これを毎回やらずにn^ε回までバッファして貯めておくだけ。これBool行列に限定してn^εじゃなくて64にするとかで使えば定数倍は便利そう | |
| ソートキラーに使う場合、最終的にトーナメントグラフっていうんだっけ、向き付きの完全グラフになって辺数全部埋まるのでe=O(v^2)なのでv^2をeに減らす類の改善の評価は無になるのだけど、逆にそれが使えそうなのだけどもはてさて | |
| "Dynamic Graph Algorithms" ていうスライドPDF: http://www.disp.uniroma2.it/users/italiano/dynamic1.pdf 読みふけっている。面白いなー。やっぱり具体的に書きたい応用が念頭にあって読むときが一番わかりやすい。 |