抄録
A-003
大規模グラフのspannerを生成するストリーミングアルゴリズムの実装
大規模グラフのspannerを生成するストリーミングアルゴリズムの実装
◎石島正大・中野眞一（群馬大）
大規模グラフGの距離を近似的に保存するように, 辺を適切に間引いた部分グラフを, グラフGのspannerという.
グラフGの2点x,y間の距離をdistG(x,y)と書く.
G=(V,E)とGのspanner G'が, 任意の2点x,y∈Vについて,
distG'(x,y) ≤ t distG(x,y)
を満たすとき, G'をGのt-spannerという.
spannerを求めるstreamingアルゴリズムが知られている.
本文はこのアルゴリズムを実装し, 様々な大規模グラフに対して, 得られるspannerの特徴を調べる.
グラフGの2点x,y間の距離をdistG(x,y)と書く.
G=(V,E)とGのspanner G'が, 任意の2点x,y∈Vについて,
distG'(x,y) ≤ t distG(x,y)
を満たすとき, G'をGのt-spannerという.
spannerを求めるstreamingアルゴリズムが知られている.
本文はこのアルゴリズムを実装し, 様々な大規模グラフに対して, 得られるspannerの特徴を調べる.