グラフとネットワークの並列アルゴリズムに関する研究

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

いくつかのグラフ・ネットワーク上の問題を解く効率の良い逐次・並列アルゴリズムを開発した.以下が主な成果である.1.直並列グラフや部分k-木上の多くの組み合わせ問題は線形時間で解けるが,辺彩色問題は直並列多重グラフ上でも今までに多項式時間のアルゴリズムが知られてない数少ない問題である.本研究では直並列多重グラフ上で辺彩色問題を線形時間で解く逐次アルゴリズムとO(log|V)時間で解く並列アルゴリズムを与えた.ここでVは与えられる直並列多重グラフの点集合である.この結果はスケジューリング問題を解く上で有用である.2.Gは無向平面グラフであり,Gの辺は非負実数の長さを持つとする.本研究ではGの2つの面の周上にk組の端子対が指定されたときに,それぞれの端子対を結び,長さの総和が最小な非交差道を求めるアルゴリズムを与えた.非交差道とは点や辺を共有するかもしれないが,互いに平面上で交差はしていない道のことである.アルゴリズムの計算時間はO(nlogn)である.ここでnは平面グラフの点数である.3.外長方形とその内部の1つの長方形(内長方形)で囲まれた平面領域をAとする.Aの内部にはr個の長方形障害物があるとする.外長方形と内長方形の周上にk組の端子対が指定されているとする.本研究ではA上でそれぞれの端子対を結び,長さの総和が最小な非交差直交道を求める効率の良いアルゴリズムを与えた.平面グラフ上の問題に帰着させて問題を解いており,アルゴリズムの計算時間はO(nlogn)である.ここでn=r+kである.このアルゴリズムはVLSIの一層配線問題等に応用できる.