部分近傍計算とその応用
8
0
0
全文
(2) 頂点 v の [s]-近傍 N[s] (v) を求める単純な方法. ある. ここで, Nt,[s] (v) は, 常に Nd (v) を含んでい. を説明する. 今, G = (V, E) を重さなし無向グラ. ることに注意してほしい. ただし, d = δ(u, v)/t. フとする. このときには, v を根とする幅優先探索. とおいている. N[s] (v) は v から近い順に頂点を. を行ない, s 個の頂点を集めた時点で終了とすれば. 集めた集合であった. 一方, N[s] (v) とは異なり,. よい. N[s] (v) を求める計算時間は O(s2 ) である. さらに, [s]-近傍を個別に求めていくことで, すべ. Nt,[s] (v) は「取りこぼし」があってもよいが, 必ず 取らなければならない部分が存在し, それらを含ん. ての頂点の [s]-近傍を O(ns2 ) 時間で求めること. で集めた集合である.. ができる. しかしながら, 個別に近傍を求めてい. 我々は問題 I を解くため, 各頂点の局所的な状. くことは効率的ではない. 例えば, 頂点 x および,. 況を保持していれば, それらの情報をもとに, 任意. y の [s]-近傍を求めることを考えたときに, N[s] (x). の頂点に対して, その頂点の [s]-近傍を近似的に求. と N[s] (y) との重なりが多い場合がある. 特に, y. めることを考えた. その結果, 我々は次の定理を示. が x に隣接する頂点であるときには, N[s] (y) 中の. した.. 要素の大部分は N[s] (x) に含まれていることが多 い. したがって, 各頂点ごとに新しく計算しなおす ことは, ほぼ同様の計算を繰り返し行なうことにな り非効率的である. また, 各頂点に対して [s]-近傍 を保存することを考えたときに, [s]-近傍どうしの 重なりを考慮せずに, 個別に保存しておくことも効 率的ではない. 以上, 単純な方法は計算時間と保存 領域の両面から効率的ではない. そこで, 我々は次 の問題を考えた. 問題 I : グラフ G = (V, E) が与えられたとき に, 任意の頂点に対して, その頂点から距離が近. 定理 1.3 与えられたグラフ G = (V, E) を重さつ き無向グラフとする. ただし, 各辺の重さ, 及び,. k は 1 以上の整数とする. このとき, グラフ G を 処理し, 高い確率でサイズ O(kn1+1/k log1−1/k n) のデータベースをつくることができる. その計算 時間は, 高い確率で O(kmn1/k log1−1/k n) 時間で ある. 構成したデータベースは, 各質問に対して. (2k − 1)-近似 [s]-近傍を答える. しかも, その近似 近傍の計算時間は高い確率で O(sn1/k log1−1/k n) 時間である.. い順に集めた [s]-近傍 (neighborhood query) ま たは, [s]-近傍を与える木 (neighbor tree query) をすばやく答えることができるように, グラフを. 注. 本論文では, 与えられるグラフが重さなし無向 グラフであるという仮定のもとで近似近傍の計算 法を示した (節 3.2). 重さつき無向グラフの場合に. 処理する.. も, 同様のアイディアを使うことができる. けれども残念ながら, 任意の頂点に対しその [s]近傍を正しく答えられるようにグラフを処理する ことは, 非常に難しいと考えている. そこで, 我々 は [s]-近傍の近似解を考えることにした. 具体的に は次のような近似近傍を考える.. 構成されたデータベースを Partial Neighbor-. hood Oracle と呼ぶことにする. 本論文では, Thorup と Zwick [2] が提案した Distance Oracle の 構成法の技術を応用する. Distace Oracle とは, グ ラフを前処理して得られる一種のデータベースで ある. これは, 任意の二頂点に対して, その近似距. ˜ ⊆ V が以下を満たすとき, v の 定義 1.2 集合 N. 離を効率よく答えることを目標にしている. 一方, 我々の Partial Neighborhood Oracle は任意の頂. t-近似 [s]-近傍 であるという.. 点に対して, その近似近傍を効率よく答えることを. ˜ | = s + 1. (1) |N. 目標にしている.. ˜, (2) ∀u ∈ N {u ∈ V | δ(u , v) <. δ(u, v) ˜. }⊆N t. 本論文は 4 節からなる. 2 節では, グラフの階層 分けに関する基本性質を説明する. 3 節では, 前節. この t-近似 [s]-近傍を Nt,[s] (v) と表すことにす. で説明した基本性質を利用した部分近傍を効率良. る. 各頂点 v に対し, Nt,[s] (v) は t = 1 のとき, [s]-. く計算するアルゴリズムを示す. 4 節では, まとめ. 近傍と一致する. すなわち, N1,[s] (v) = N[s] (v) で. と応用例について述べる.. −48− 2.
(3) 準備. 2. bunch の大きさについて以下の補題が成り立つ.. 本論文では, Thorup と Zwick の結果 [2] を使 い, 部分近傍の近似を計算している. そこで, 本節 では Zwick らにより示されたグラフの階層分けに 関する基本性質を説明する. また, 階層分けを利用. 補題 2.1 ([2]) すべての頂点 v ∈ V に対して, B(v) の平均サイズは高々 kn1/k である. さらに, Ai を構成するときに用いる確率を n−1/k. した近似距離の計算法について紹介する. 以下の. から (n/ ln n)−1/k に変更すると次の補題が成り. 結果は, [2] に示されている.. 立つ. 補題 2.2 ([2]) 高い確率で, 各頂点 v に対する. 2.1. B(v) の大きさは O(n1/k log1−1/k n) である.. グラフの階層分け. 加列 A0 ⊇ A1 ⊇ · · · ⊇ Ak−1 ⊇ Ak (k は正の整. 証明. p = (n/ ln n)−1/k とする. 各頂点 v に対 k−1 して, B(v) の大きさは和 i=0 Xi により上から. 数) を考える. Ai は Ai−1 中の各頂点を, それぞ. 抑えられる. ここで, Xk−1 は n と pk−1 をパラ. 無向グラフ G = (V, E) が与えられたとき, 非増. れ独立に確率 n. −1/k. で選び, 構成された頂点の集. 合とする. ただし, A0 = V , Ak = ∅ とする. 各. メータとして持つ二項分布に従う確率変数を表し,. Xi (0 ≤ i ≤ k − 2) は p をパラメータとして持つ幾. i (0 ≤ i < k) に対して, Ai の平均サイズは n1−i/k. 何分布に従う確率変数を表す. また, k 個の確率変. である. また, Ai の要素を i-center と呼ぶ.. 数は互いに独立である.. 以下では, 議論を単純にするため, Ak−1 = ∅ であ ると仮定する. 各頂点 v に対して bunch B(v) ⊆ V を次のように定める. w ∈ Ai −Ai+1 (0 ≤ i ≤ k−1). X を二項分布に従う確率変数とし, その期待値 E[X] を µ と書くことにする. このとき, 次の不等 式が成り立つ. (Chernoff’s bounds [5]). が, δ(w, v) < δ(Ai+1 , v) を満たすとき, かつそのと きに限り, B(v) の要素とする. すなわち, w は Ai+1. Pr{X > (1 + δ)µ} <. 中のどの頂点よりも v に近い頂点である. ここで,. δ(Ak , v) = ∞ であるから, すべての頂点 v ∈ V に. Pr{X < (1 − δ)µ} < e−µδ. 対して, Ak−1 ⊆ B(v) であることに注目してほし い. また, pi (v) ∈ Ai を v に最も近い頂点, すなわ. µ eδ . (1 + δ)1+δ 2. /2. .. まず, E[Xk−1 ] = npk−1 = n1/k ln1−1/k n であ. ち δ(pi (v), v) = δ(Ai , v) を満たす頂点とする. し. るから, はじめの不等式に対して, δ = 3, µ =. たがって, すべての頂点 v に対して, δ(A0 , v) = 0. n1/k ln1−1/k n を代入すると,. であり p0 (v) = v となる. 図 2 は k = 3 のときの 頂点 v に対する B(v) を表したものである. 黒の. 1/k. Pr{Xk−1 > 4n1/k ln1−1/k n} < (e3 /44 )n 1/k. < e−2n. 頂点は A2 を表す. また 灰色と白の頂点はそれぞ れ A1 − A2 および, A0 − A1 の頂点を表す.. ln1−1/k n. ln1−1/k n. < e−2 ln n = n−2 となる. ここで, 任意の s に対して, 以下が成り. p2 (v). 立つ.. p1 (v). Pr{ v. k−2 . Xi > s} ≤ Pr{B(s, p) < k}.. i=0. ただし, B(s, p) は s と p をパラメータとしてもつ 二項分布の確率変数とする. したがって,. Pr{. k−2 . Xi > 16n1/k ln1−1/k n}. i=0. ≤ Pr{B(16n1/k ln1−1/k n, (n/ ln n)−1/k ) < k}. 図 2 : k = 3 のときの B(v). −49− 3.
(4) となる. さらに,. µ = E[B(16n1/k ln1−1/k n, (n/ ln n)−1/k )] = 16 ln n であることに注意する. k ≤ log n であるとすると,. k < µ/2 となり, 二つ目の不等式に対して, δ = 1/2 とすると, 次式を得る. Pr{. k−2 . u および v である. また, w0 = u0 , δ(w0 , u0 ) = 0 となる. i 回目の繰り返しで while ループの条 / B(vi−1 ) であり, 件式を満たしたとすると, wi ∈ δ(wi−1 , vi−1 ) ≥ δ(Ai , vi−1 ) = δ(pi (vi−1 ), vi−1 ) となる. ところで, vi−1 = ui , wi = p(ui ) あるから,. δ(wi , ui ) = δ(pi (ui ), ui ) = δ(pi (vi−1 ), vi−1 ) ≤ δ(wi−1 , vi−1 ). Xi > 16n1/k ln1−1/k n} < e−µ/8 = n−2. ≤ δ(wi−1 , ui−1 ) + ∆. i=0. 以上より, 少なくとも 1 つの B(v) のサイズが. 20n1/k ln1−1/k n を越える確率は, 高々 n(n−2 + n−2 ) = 2/n 1 である.. 2.2. が成り立つ.. さらに, Ak−1 ⊆ B(v) であるか. ら, 繰り返し回数は高々 k 回である.. ゆえに,. δ(w, u) ≤ (k − 1)∆ となる. よって, δ(w, v) ≤ δ(w, u) + δ(u, v) ≤ (k − 1)∆ + ∆ ≤ k∆ が成り 立つ. 以上より、見積もり値 distk (u, v) は, 高々. 近似距離の計算. (2k − 1)∆ となる.. . 以下に示すアルゴリズムは任意の二頂点に対し て, bunch を利用してその頂点間距離の 2k − 1 倍 以内の距離を求めることができる. ただし, k は正 の整数. ここでは, 任意の二頂点間距離が与えられ ているものとし, また各頂点の bunch は計算して あるものとする.. 部分近傍の近似計算. 3. 本節では, 部分近傍を近似的に計算するアルゴリ ズムについて説明する. 節 3.1 では, 与えられたグ ラフを前処理するアルゴリズムを示す. 前処理に より構成されたデータベースを用いて, 実際に部. アルゴリズム distk (u, v). 分近傍の近似を求めるアルゴリズムを節 3.2 で説. w → u; i → 0. 明する. そして, 前処理を行なうアルゴリズムの解. while w ∈ / B(v). 析を節 3.3 で与える. 最後に 節 3.4 で構成される. i→i+1 (u, v) → (v, u). データベースが効率のよい spanner でもあること を説明する.. w → pi (u) return δ(w, u) + δ(w, v). 3.1. グラフの前処理. bunch の構成法からアルゴリズムは高々 O(k) 時間で終了することに注意してほしい. このアル. グラフを前処理するアルゴリズムは以下のよう になる. このアルゴリズムは, [2] で提案されたア. ゴリズムは以下の補題を満たす.. ルゴリズムにおいて Ai を構成する際に使う確率を 補題 2.3 ([2]) distk (u, v) ≤ (2k − 1)δ(u, v).. (n/ ln n)−1/k に変更したものである.. 証明. 与えられるグラフが無向グラフであることか ら, u, v を交換する操作により, その二頂点間の距 離 ∆ = δ(u, v) は変化しない. while ループに入 る前, w = u なので δ(w, u) = 0 となる. 以下, 各 繰り返しにおいて, δ(w, u) の値が高々 ∆ しか増え ないことを示す. 今, ui , vi , wi を i 回目の繰り返しのとき, u, v, w に与えられている値とする. したがって, u0 , v0 は. −50− 4. 入力として無向グラフ G = (V, E) が与えられ たとする. アルゴリズム preprok (V, E) は, まず 非増加列 A0 ⊇ A1 ⊇ · · · ⊇ Ak−1 ⊇ Ak を構成す る. Ai は Ai−1 中の各頂点を, それぞれ独立に確率. (n/ ln n)−1/k で選び, 構成された集合である. ただ し, A0 = V , Ak = ∅ とし, Ai の要素を i-center と 呼ぶことにする..
(5) る. pi+1 (v) ∈ B(v) であるとする. (∗) の条件文が アルゴリズム preprok (V, E). 成り立てば, pi (v) = pi+1 (v) ∈ B(v) となる. 成り. A0 ← V ; Ak ← ∅ for i ← 1 to k − 1. 立たない場合, δ(pi (v), v) = δ(Ai , v) < δ(Ai+1 , v) となり, B(v) の定義から, pi (v) ∈ B(v) となる. . Ai は Ai−1 の各要素を独立に, 確率 (n/ ln n)−1/k で選び, 構成する. δ(Ak , v) ← ∞ for i ← k − 1 down 0. に対して, cluster C(w) を構成する. cluster C(w) は, 他のどの (i + 1)-center よりも w の方が近. for 各 v ∈ V , δ(Ai , v) を計算し, pi (v) ∈ Ai を見つける.. くにある頂点から成る. すなわち, C(w) = {v ∈. V | δ(w, v) < δ(Ai+1 , v)} である. ここで, すべて の頂点 v ∈ V に対して, δ(Ak , v) = ∞ であるか. ただし, δ(pi (v), v) = δ(Ai , v) .. if δ(Ai , v) = δ(Ai+1 , v) then pi (v) ← pi+1 (v). 次に, アルゴリズムは各 i-center w ∈ Ai − Ai+1. ら, 各頂点 w ∈ Ak−1 に対し, C(w) = V となるこ. (∗). for 各 w ∈ Ai − Ai+1 , w から C(w) 覆うまで最短経路木 T (w) を広. とに注目してほしい. 前節で説明した bunch と本節の cluster は互い に逆の関係にあることが容易にわかる. すなわち, 任意の v, w に対して v ∈ C(w) のとき, かつその. げる. ただし, C(w) = {v ∈ V | δ(w, v) < δ(Ai+1 , v)}.. ときに限り, w ∈ B(v) が成り立つ.. for 各 v ∈ V , B(v) ← {w ∈ V | v ∈ C(w)}.. 各 cluster C(w) は Thorup のアルゴリズムの一 部を変更したアルゴリズムを利用することにより, 計算することができる. しかし, このアルゴリズム. アルゴリズムの主要部分は k 回の繰り返しから 成る. i 回目の繰り返しにおいて, すべての頂点. v ∈ V に対し, 距離 δ(Ai , v) を計算する. ただし, δ(Ai , v) = min{δ(w, v) | w ∈ Ai } である. これら の値は, 次のようにして求めることができる. グラ フ G = (V, E) に新しい頂点 vnew および, vnew と Ai の各頂点を結ぶ重さ 0 の辺を加える. そして,. vnew を始点として, その他の頂点との距離を計算 する. それらの距離は, Thorup のアルゴリズムを 利用して O(m) 時間で計算することができる [4]. そのうえ, アルゴリズムが構成する最短経路木によ り, δ(pi (v), v) = δ(Ai , v) を満たす頂点 pi (v) ∈ Ai を容易に求めることができる. 一般に, v との距離が δ(Ai , v) に等しい頂点は. Ai 中に複数存在する. そこで, 複数存在した場合 には (∗) のように pi (v) を定めることにする. 各頂 点 v に対して pi (v) をこのように定めると以下の 性質を満たす.. は複雑なので, 代わりに Dijkstra のアルゴリズム を修正したアルゴリズムを使い, 説明する. 同様の 修正は Thorup のアルゴリズムにも施すことがで きる.. Dijkstra のアルゴリズムの修正 始点を w としたときに, Dijkstra のアルゴリズム は, それぞれの頂点 v に対して, 距離 δ(w, v) の上限 値 d(v) を保持する. 初期状態では, d(v) = ∞ とし ておく. はじめに, d(w) = 0 とし, その他の頂点は 距離を決定しない. 各繰り返しでは, まだ最終的な 最短路の重みが決定していない頂点の中で, 最小の. d(u) を持つ頂点 u に対して, 経路の重みを決定し, u に接してる辺を緩和する. すなわち各辺 (u, v) ∈ E に対し, d(v) ← min{d(v), d(u) + (u, v)}. ただし,. (u, v) は辺 (u, v) の重さを表す. 最終的にすべて の頂点の最短路の重みが決定するまでこれを繰り 返す.. 補題 3.1 すべての v ∈ V , 0 ≤ i ≤ k − 1 に対し. ここで, Dijkstra のアルゴリズムの緩和操作を次 のように変更する. d(u) + (u, v) < δ(Ai+1 , v) の. て, pi (v) ∈ B(v) .. とき, かつそのときに限り, 辺 (u, v) を緩和する. 証明. i に関する帰納法により示す. i = k − 1 のと. δ(Ai+1 , v) の値は前に計算しているので, 上記の不. き, すべての v ∈ V に対して, pk−1 (v) ∈ Ak−1 ⊆. 等式が成り立つか否かを定数時間で調べることが. B(v) であるから成り立つ. i < k − 1 について考え. できる. このように修正した Dijkstra のアルゴリ. −51− 5.
(6) ズムを Modified Dijkstra’s Algorithm と呼ぶこと にする.. 3.2. 部分近傍の答え方. 与えられた頂点の [s]-近傍の近似を求めるアル ゴリズムは以下のようになる. ただし, 節 3.2 では. 補題 3.2 Modified Dijkstra’s Algorithm は頂点. 入力として与えられるグラフを重さなし無向グラ. w ∈ V に対して C(w) に属するのすべての頂点 を訪れ, w からそれらの頂点との最短距離を計算. フであると仮定する. アルゴリズム partial-neighbor(u, s). する.. N (u) ← ∅; r ← 0 補題 3.2 は Dijkstra のアルゴリズムの証明と同 様にして証明することができる. したがって, Mod-. ified Dijkstra’s Algorithm により, C(w) を求める ことができる. さらに, C(w) を覆う最短経路木 T (w) を構成するようにアルゴリズムを容易に変更 できる. そのように変更しても, アルゴリズムの計 算時間は変わらない.. while |N (u)| ≤ s r ←r+1 for 各 w ∈ B(u) , {v ∈ T (w) | δT (w) (u, v) = r} 中の新 しくでてきた頂点を順に N (u) に加 える. ただし, δT (w) (u, v) とは T (w) 上での u と v との距離を表す.. return N (u). 一般に, Dijkstra のアルゴリズムを単純に実行す る場合には, まだ最短路の重みが決定していない頂 点の値 d(v) を管理するため 2 分ヒープを使う. 2 分 ヒープを使うことで, 最小の d(v) をもつ頂点 v を. w1. 見つけ, d(v) を削除することが O(log n) 時間で実 現できる. この二つの作業はそれぞれ, 高々 n−1 回 および, m 回行なわれる. 以上より, 与えられた始点 に対し, 元々の Dijkstra のアルゴリズム全体の計算 時間は O((m+ n) log n) となる. したがって, C(w) を求めるのにかかる計算時間は O(|E(C(w))| log n) となる. ここで, E(C(w)) とは, C(w) 中の頂点と 接している辺の集合を表す. さらに, [6] に述べられ ているようにフィボナッチヒープを用いると, 全体. ···. ··· ···. w2. .. ···. の計算時間が O(|E(C(w))| + |C(w)| log n) になる.. Thorup のアルゴリズム [4] も同様に変更する ことができ, それぞれの頂点 w に対して, cluster. C(w) を O(|E(C(w))|) 時間で計算することがで きる.. 図 3 : r = 1 のときの例 頂点 u の [s]-近傍の近似を求めることを考える. アルゴリズム partial-neighbor(u, s) は各繰り返 しにおいて, それぞれの木 T (w) の中で u からの距. 最後に, preprok (V, E) が構成する T (w) の大き. 離 r の頂点を N (u) に加えていく. ここで, cluster. さについて説明する. 各頂点 w に対して, T (w) の. と bunch の関係から, 木 T (w) 中に必ず u が存. 大きさの総和は, cluster 全体の大きさ, すなわち,. 在するので, u から距離 r の頂点を容易に見つけ. bunch 全体の大きさに等しい. なぜならば, 定義よ. ることができる. 今, 与えられたグラフが重さなし. り v ∈ C(w) のとき, かつそのときに限り w ∈ B(v) が成り立つので, w∈V |C(w)| = v∈V |B(v)| と. 無向グラフであるから, T (w) の中で u から距離 r. なるからである. 補題 2.2 から T (w) の大きさの. の根から r 段目にある頂点である. 図 3 は r = 1. 総和は, 高い確率で O(kn1+1/k log1−1/k n) である.. preprok (V, E) の計算時間の解析については節 3.3 で行なう.. −52− 6. の頂点は T (w) を, u を根とした木を考えたとき としたときのアルゴリズムの動きを表す. 図 3 に あるようにアルゴリズムは 各 T (w) の r 段目の 頂点をすべて取り終えてから r + 1 段目に進むこ.
(7) とに注意して欲しい. 調べていく中で, すべての頂. ると, d˜ ≥ d˜∗ である. このとき, d∗ ≤ d˜∗ ≤ d˜ ≤. 点を取り終えた木があれば, それ以降, その木を除. (2k − 1)d となるので, d∗ /(2k − 1) ≤ d である. こ. いて繰り返し調べていく. 以下, 集めた頂点の総数. の対偶は, N (u) が (2k − 1)-近似 [s]-近傍であるこ. が s 個に到達するまで繰り返し, s 個の頂点を集め. とを示している.. た時点で終了する. pk−1 (u) ∈ B(u) を根とする木. 次に, アルゴリズムの計算時間について説明す. T (pk−1 (u)) は全域木なので, 任意の s (≤ n) に対. る.. して必ず s 個の頂点を集めることができる.. から, preprok (V, E) で構成した木の集合 T =. さらに, 頂点を集めるだけでなく, 集めた頂点を つなぐ木をつくることもできる. はじめに, 頂点 u だけから成る木を考える. 新らたに頂点 v ∈ T (w) を発見した場合, いままでに構成した木の中の, 木. 補題 2.2 および, bunch と cluster の関係. {T (w) | w ∈ V } に対し, 高い確率で, すべての 頂点は O(n1 /k log1−1/k n) 個の木の中にしか表れ ない. したがって, u から木をたどりながら s 個 の頂点を集めるために調べなければならない頂点. T (w) 上での v の親にあたる頂点の直下に v をつ け加える. 頂点が s 個集まるまで, 繰り返し頂点を. の個数は, O(s · n1/k log1−1/k n) 個である. すな. つけ加えることで集めた頂点をつなぐ木をつくる. O(s · n1/k log1−1/k n) である.. ことができる. 補題 3.3 ∀v ∈ V , ∃w ∈ B(u),. わち, s 個の頂点を集める計算時間は, 高い確率で. 3.3. . 前処理をするアルゴリズムの解析. δ(w, v) + δ(w, u) ≤ (2k − 1)δ(v, u) 先に述べたように, 頂点 w に対して C(w) を この補題は, 補題 2.3 から明らかなので証明は省 略する.. 求めるのにかかる時間は, O(|E(C(w))|) である. もしくは, Dijkstra のアルゴリズムを利用すると,. 補題 3.4 アルゴリズ ム partial-neighbor(u, s) が v ∈ T (w) をはじめて取るとする. このとき,. O((|E(C(w))| + |C(w)|)) log n) となる. E(C(w)) とは C(w) 中の頂点に接している辺の集合のこと である. 今, E(v) を頂点 v に接している辺の集合. δT (w) (u, v) ≤ (2k − 1)δ(u, v).. とすると, すべての頂点の cluster を求める時間は. 証明. v に対して w∗ を補題 3.3 を満たすものとす. 以下の式で抑えられる.. る. このとき,. . δT (w) (u, v) =. min δT (w ) (u, v). w ∈B(u). w∈V. ≤ δT (w∗ ) (u, v) ≤ (2k − 1)δ(u, v). . |E(C(w))| ≤. |E(v)|. w∈V, v∈C(w). . =. |E(v)|. v∈V, w∈B(v). . となる.. =. を求めることができる. また その計算時間は, 高 い確率で O(s · n1/k log1−1/k n) である. 証明. アルゴリズム partial-neighbor(u, s) が 最後にとった頂点を v ∗ とし, v ∗ ∈ T (w∗ ) で あったとする. δT (w∗ ) (u, v ∗ ) を d˜∗ とおく. ま た, δ(u, v ∗ ) = d∗ とする. 補題 3.4 から d˜∗ ≤. (2k − 1)δ(u, v ∗ ) が成り立つ.. (|B(v)| · |E(v)|). v∈V. 補題 3.5 アルゴリズ ム partial-neighbor(u, s) は, 頂点 u の (2k − 1)-近似 [s]-近傍 N2k−1,[s] (u). . 補題 2.2 から, 高い確率で各頂点 v の |B(v)| の 大きさは O(n1/k log1−1/k n) であるから,. . O(n1/k log1−1/k n)|E(v)|. v∈V. = O(mn1/k log1−1/k n).. アルゴリズムで取. また, その他の部分の計算には高々 O(km) しかか. られなかった頂点 v について考える. 今 v に対 し, minw∈B(u) δT (w) (u, v ) = d˜ , d = δ(u, v ) とす. からない. したがって, アルゴリズム全体の計算時. −53− 7. 間は, O(kmn1/k log1−1/k n) となる..
(8) 3.4. 疎な spanner と tree cover. 補題 2.3 と節 3.2 から, preprok (V, E) が構成. 最後に, 今回提案した Partial Neighborhood Oracle の応用例について簡単に説明する. Aingworth,. する木の集合 T (w) について, 次の系が成り立つ.. Chekuri, Indyk, Motwani [1] は任意のグラフに対 し, そのグラフの直径の近似値を求める多項式時. 系 3.6 preprok (V, E) が各頂点 w ∈ V に対して. 間アルゴリズムを提案した. 我々は, 部分近傍を効. 構成する木 T (w) の集合は G = (V, E) の (2k −1)-. 率よく計算することで, アルゴリズム全体の計算. spanner を形成する. この (2k − 1)-spanner の大 きさは, 高い確率で, O(kn1+1/k log1−1/k n) であ. 時間を短縮させられることを示した. そこで, 与. る. また, O(kmn. 1/k. log. 1−1/k. n) 時間で計算する. ことができる.. えられるグラフが無向グラフであるとし, Partial. Neighborhood Oracle の利用を考えた. その結果, 直接利用することはできなかったが, アルゴリズム preprok (V, E) が構成する (2k − 1)-spanner を利. ここで, spanner とは次のように定義される.. 用し, 計算時間を短縮することができた. その一方,. 定義 3.7 G = (V, E) に対して, その部分グラフ. G = (V, H), ただし H ⊆ E, が以下を満たすと き, κ-spanner であるという.. 直径の近似精度は悪くなってしまった. 今後の課 題とし ては, より効 率よく Partial. Neighborhood Oracle を構成することがあげら れる.. ∀u, w ∈ V, δH (u, w) ≤ κ · δ(u, w).. 参考文献. ただし, δH (·) とは H 上の距離を表す. また, 系 3.6 と補題 2.2 から次の系が得られる. 系 3.8 preprok (V, E) で構成される T (w) の集合 は, 次の二つの性質を満たす G に対する tree cover を形成する.. • 高い確率で, 各頂点は O(n の木の中にしか現れない.. and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999.. 1/k. log. 1−1/k. n) 個. [2] M. Thorup and U. Zwick. Approximate distance oracles. In Proc. 33rd ACM Symposium. • 任意の二頂点 u, v ∈ V に対して, その二頂 点間距離の高々2k − 1 倍の長さをもつパス を含む木 T (w) が存在する. また, その木を. O(k) 時間で探索することができる. 上記の二つの系は, Partial Neighborhood Ora-. cle の応用例を説明する際に重要な役割を果たす. 応用例については, 節 4 で簡単に説明する.. 4. [1] D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. Fast estimation of diameter. on Theory of Computing, 2001 [3] S. Basawana and S. Sen. Approximate Distance Oracles for Unweighted Graphs in O(n2 log n)Time. In Proc. 15th Annual ACMSIAM Symposium on Discrete Algorithms , 2004 [4] M. Thorup. Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM, 46:362-394, 1999.. まとめ 本論文では, [s]-近傍という新しい近傍の概念を. 考え, [s]-近傍の近似を効率よく計算する方法につ いて考えた. その結果, 我々は Partial Neighbor-. [5] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.. hood Oracle を提案し, 任意の頂点に対して, その 頂点からの距離が近い頂点を集めた近似近傍とそ. [6] M.L. Fredman and R.E. Tarjan. Fibonacci heaps and their uses in improved network op-. れらの頂点をつなぐ木を効率よく答えられるよう. timization algorithms. Journal of the ACM, 34:596-615, 1987.. に, グラフを処理できることを示した.. −54− 8.
(9)
関連したドキュメント
基本波を用いる近似はピクセル単位の時間放射能曲線に対しては用いることができる
Eckstein: Dual coordinate step methods for linear network flow problems, Mathematical Programming 42 (1988)
東京工業大学
TCPA Time to Closest Point of Approach の略称.
9/21 FOMC 直近の雇用統計とCPIを踏まえて、利上げ幅が0.75%になるか見 極めたい。ドットチャートでは今後の利上げパスと到達点も注目
アメリカの FATCA の制度を受けてヨーロッパ５ヵ国が，その対応につ いてアメリカと合意したことを契機として， OECD
