nojima718 https://blog.hatena.ne.jp/nojima718/ @nojima's blog https://nojima.hatenablog.com/ 授業で論文紹介したので，ここにメモ． 『GConnect: A Connectivity Index for Massive Disk-Resident Graphs』は，巨大なグラフに対してインデックスを作って，辺連結度クエリに高速に答える手法について議論した論文です．以下のような問題を考えます． 巨大なグラフGが与えられる．(例えば，頂点数10万，辺数100万とか)G内の任意の2点s, tが与えられたとき，sとtの辺連結度を高速に計算せよ． 2頂点の辺連結度というのは，グラフから最小で何本辺を取り除けば，その2頂点を非連結にできるかで定義される量です． 計算時間を気にしなければ，最大 s-… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnojima.hatenablog.com%2Fentry%2F2011%2F12%2F10%2F162332" title="[論文紹介] GConnect: A Connectivity Index for Massive Disk-Resident Graphs - @nojima&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> http://img.f.hatena.ne.jp/images/fotolife/n/nojima718/20111210/20111210154539.png Hatena Blog https://hatena.blog 2011-12-10 16:23:32 rich https://nojima.hatenablog.com/entry/2011/12/10/162332 1.0 100%