ネットワーク上の並列-分散アルゴリズムに関する研究

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

いくつかのグラフ・ネットワーク上の問題を解く効率の良いアルゴリズムを開発した.以下が主な成果である。1.VLSIの1層配線問題には,2次元平面領域においていくつかの端子対を結ぶ互いに交差しない長さの総和が最小な道を求める問題がよく現われる.ここで"交差しない"とは,同じ点や線分を通るかもしれないが平面上では交差しないことである.一方,平面領域上の問題の多くが平面グラフ上の問題に帰着される.本研究では平面グラフの2つの面の周上にいくつかの端子対が指定されている場合にそれらの端子対を結ぶ"交差しない"道で長さの総和が最小であるものを求めるアルゴリズムを与えた.アルゴリズムの計算時間はO(nlogn)である.ここで,nはグラフの点数である.2.平面上で指定した2点の結び障害物を通らない道で長さが最小なものを求める問題はさまざまな場面で現われる.本研究では障害物の形状を軸平行多角形に限定し,先に障害物が与えられて前処理が可能である場合のアルゴリズムを与えた.前処理に要する時間はO(n^2log^2n)であり,2点が与えられた時にそれらを結ぶ最短路をO(log^2n)時間で求めることができる.