相互結合網における効率的な経路選択アルゴリズムの開発

点击翻译按钮获取中文摘要

本年度は,超並列分散計算機の相互結合網に適したふたつの位相,バブルソートグラフ,焦げたパンケーキグラフにおける互いに素な経路問題,ハミルトン閉路・経路を解くアルゴリズムを開発した.以下にその詳細を記す.1 バブルソートグラフにおける頂点から頂点集合への互いに素な経路問題バブルソートグラフにおいて,頂点から頂点集合への互いに素な経路問題を多項式時間で解くアルゴリズムを開発した.n-バブルソートグラフにおける提案アルゴリズムの時間計算量はO(n^5)である.電子情報通信学会論文誌にて発表した.2 焦げたパンケーキグラフにおけるハミルトン閉路・経路問題焦げたパンケーキグラフにおいて,ハミルトン閉路および経路を生成するアルゴリズムを開発した.また,グラフ内にひとつの故障頂点が存在するときにもハミルトン閉路を生成するアルゴリズムも併せて提案した.並列分散計算システムに関する国際会議にて発表した.3 焦げたパンケーキグラフにおける二頂点間の内素な経路問題焦げたパンケーキグラフにおいて,二頂点間の内素な経路問題を多項式時間で解くアルゴリズムを開発した.n-焦げたパンケーキグラフにおける提案アルゴリズムの時間計算量はO(n^3)である.電子情報通信学会技術研究報告および並列分散処理・応用に関する国際シンポジウム(ISPA '05)にて発表した.