格子グラフ上の最短経路問題のための劣線形領域アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• グラフの最短経路問題は数多くの応用をもつ非常に重要な問題の一つである.しかし,これまでに提案されてきた最短経路アルゴリズムはグラフの頂点数に比例する空間計算量を必要とするものが多く,劣線形領域のアルゴリズムはほとんど知られていない.本論文では,格子グラフ上の二頂点間の最短経路を頂点数nの劣線形サイズの作業領域で求めるアルゴリズムを提案する.提案アルゴリズムは,自然数パラメータlをとって,O(n^<(2^l)/(2^<l+1>-1)>)の空間計算量,およびO(n^<(2^l(l+2))/(2^<l+1>-1)>)の時間計算量で動作する.

• 2012-03-09

著者

• 今井 達也

  東京工業大学大学院総合理工学研究科材料物理科学専攻

• 今井 達也

  東京工業大学大学院情報理工学研究科数理計算科学専攻

• 野口 俊輔

  東京工業大学理学部情報科学科

• 藤 哲郎

  東京工業大学理学部情報科学科

• 今井 達也

  東京工業大学大学院情報理工学研究科数理・計算科学専攻

• 今井 達也

  東京工業大学大学院情報理工学研究科:日本学術振興会特別研究員

• 今井 達也

  東京工業大学 大学院情報理工学研究科 数理・計算科学専攻

• 藤 哲郎

  東京工業大学 理学部 情報科学科

関連論文

• 骨肉腫におけるOB-カドヘリン遺伝子の発現
• Cu-15 mass%Cr 複相合金圧延材における引張特性の異方性
• 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム (コンピュテーション)
• 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム (アルゴリズムと計算理論の新展開)
• 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム
• DS-1-4 輸送型古典的プランニング問題のための近似アルゴリズムと許容的ヒューリスティック(DS-1.COMP学生シンポジウム,シンポジウムセッション)
• 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム

スポンサーリンク