文献

J-GLOBAL ID：201302286630679805   整理番号：13A1371316

疎グラフにおける最適分岐問題に対する一定時間近似アルゴリズム

Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs

著者 (3件)： KUSUMOTO Mitsuru (Kyoto Univ.) ,  YOSHIDA Yuichi (National Inst. of Informatics) ,  ITO Hiro (Univ. Electro-Communications)
資料名： International Journal of Networking and Computing  (International Journal of Networking and Computing)
巻： 3  号： 2  ページ： 205-216  発行年： 2013年07月 
JST資料番号： L8295A  ISSN： 2185-2839  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： WWWグラフ,ソーシャルネットワーク,ゲノムデータといった大量データを扱う分野では実行時間が入力サイズに独立な一定時間アルゴリズムが研究されている。本論文では,データ圧縮のような多くのアプリケーションを持つ有向グラフの最適分岐問題に対し,有向グラフGの最大重みの分岐を見つける一定時間アルゴリズムを提案した。まず,前記重みを近似するアルゴリズムを設計するために,最適分岐問題に対するEdmondの多項式時間アルゴリズムを説明した。次に,オラクルモデルとして本来は無向グラフに対して設計された一般グラフモデルを重み付き有向グラフを扱えるように修正し,Gの頂点数をn,0<ε<1/2のとき絶対誤差が高々εnとなる(1,εn)近似アルゴリズムを提案した。本アルゴリズムはGの平均次数をdとするとき質問計算量がO(d/ε³)であり,下界がΩ(d/ε²)となることを示した。また,本アルゴリズムは重みのない有向グラフに制限されるとき,質問計算量O(1/ε⁴)(ε>0)を持つ(1,εn)近似アルゴリズムに修正できることを説明した。その一方,重み付き有向グラフでの最小(あるいは最大)全域有向木の重みを近似するためには,少なくともΩ(n)の質問が必要なことを示した。

シソーラス用語： *最適化問題 ,  枝分れ ,  *近似法 ,  計算機アルゴリズム ,  *グラフ ,  数学的性質 ,  粒度 ,  アルゴリズム ,  *計算量 ,  重みづけ ,  有向グラフ ,  スパンニング木
準シソーラス用語： *最適分岐問題 ,  分岐 ,  近似アルゴリズム ,  *疎グラフ ,  スパース性 ,  細粒度 ,  多項式時間アルゴリズム

分類 (4件)： その他のオペレーションズリサーチの手法  (KA03070E) ,  数値計算  (JE02000J) ,  グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： グラフ ,  分岐 ,  近似アルゴリズム