◎今井達也（東工大）

二頂点対最短経路問題は，与えられた辺コスト付きグラフおよびその頂点 s, t に対して，s から t への最小コストの経路を求める問題である．本論文では，Barnes らの有向グラフのための多項式時間 o(n) 領域連結性判定アルゴリズムを拡張し，一般的な辺コスト付き有向グラフのための多項式時間 o(n) 領域最短経路アルゴリズムを提案する．このアルゴリズムはグラフ族を限定しない辺コスト付き有向グラフに対する最初の多項式時間 o(n) 領域最短経路アルゴリズムである．