グラフ上の一群の不動点問題とその逐次型解法

スポンサーリンク

概要

論文の詳細を見る
最短路問題やデータフロー解析に代表されるグラフ上の一連の問題が,不動点問題として統一的に定式化できることを示す.定式化には,情報の代数的な構造を表すのに束を用い,グラフの頂点に結び付けられた束の要素を値とする未知数に対する,不動点方程式として記述する.次に,統一的に記述された問題に対する,実用的な逐次型解法を与える.このアルゴリズムは,最短路問題に対しては,ポテンシャル法として知られる既存の方法に帰着するが,ここで定式化した枠組みの中で,これが正しく動作することは自明ではない.そこで,その正当性および停止性の証明を与える.最後に,この定式化と他の定式化との関係および最も基本的な形への一般化を考察する.また,一般化アルゴリズムと個別の分野における方法との関係を考察し,特にデータフロー解析に対しては,既存のKildallやHecht&Ullmanなどの逐次型アルゴリズムの改良になっていることを示す.
社団法人電子情報通信学会の論文
1993-01-25

著者

関連論文

スポンサーリンク