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

摘要

グラフの最短経路問題は数多くの応用をもつ非常に重要な問題の一つである．しかし，これまでに提案されてきた最短経路アルゴリズムはグラフの頂点数に比例する空間計算量を必要とするものが多く，劣線形領域のアルゴリズムはほとんど知られていない．本論文では，格子グラフ上の二頂点間の最短経路を頂点数n の劣線形サイズの作業領域で求めるアルゴリズムを提案する．提案アルゴリズムは，自然数パラメータlをとって，O((n~2~1)/(n~(2~(l+1)-1)))の空間計算量，およびO((n~2(1+2))/(n~(2~(l+1)-1)))の時間計算量で動作する．%The shortest path problem is one of the most important problem in computer science and has many practical applications, although many shortest path algorithms proposed in previous work need memory space which is proportional to the number of vertices in the graph. In this paper, we propose a sublinear space algorithm computing a shortest path betweenrntwo vertices in a grid graph. This algorithm uses O((n~2~1)/(n~(2~(l+1)-1))) words and runs in O((n~2(1+2))/(n~(2~(l+1)-1))) time where n is the number ofrnvertices and l is a parameter.