3次元VLSIレイアウト設計アルゴリズムに関する研究

3次元VLSI設計に関して種々の理論的観点から調査・検討を行ない,問題点を明らかにした.更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した.1.均等辺彩色問題で,従来より知られているO(km^2)時間のアルゴリズムを更に発展させ,より効率の良いO(m^2/k+mn)時間のアルゴリズムを与えた.ここでnはGの点数,mは辺数である.2.f-辺彩色が通常の辺彩色アルゴリズムを用いて求めることができることを示し,次いで,多重グラフのf-辺彩色問題が単純グラフの通常の辺彩色問題に容易に多項式時間で帰着できることを示した.3.直並列グラフを一般化した部分k木に対してf-辺彩色問題を線形時間で解く逐次アルゴリズムを与えた.また,O(n/logn)個のプロセッサを用いてO(logn)時間でf-辺彩色問題を解く最適な並列アルゴリズムも与えた.ここでnは入力の大きさである.本アルゴリズムはこれまで知られていなかったものであり重要な成果である.4.2次元平面上にいくつかの障害物および二層配線領域があるときに,指定された2組の端子対を結ぶ2本の道で長さの和が最小なアルゴリズムをO(nlogn)時間,O(n)の記憶量で求めた,ただし,障害物および二層配線領域は軸平行な長方形であるとする.5.平面領域A内でそれぞれの端子対を結ぶ直交線分からなるk本の道で,互いに交差せず,長さの総和が最小なアルゴリズムをO(nlogn)時間で求めた.ここではn=r+kである.ただし,長方形の内部にr個の長方形障害物がある平面領域Aにおいて,k個の端子対が外側の長方形の周および内部の一つの長方形障害物の周にのみあるとする.

3次元VLSI設計に関して種々の理論的観点から調査・検討を行ない,問題点を明らかにした.更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した.1.均等辺彩色問題で,従来より知られているO(km^2)時間のアルゴリズムを更に発展させ,より効率の良いO(m^2/k+mn)時間のアルゴリズムを与えた.ここでnはGの点数,mは辺数である.2.f-辺彩色が通常の辺彩色アルゴリズムを用いて求めることができることを示し,次いで,多重グラフのf-辺彩色問題が単純グラフの通常の辺彩色問題に容易に多項式時間で帰着できることを示した.3.直並列グラフを一般化した部分k木に対してf-辺彩色問題を線形時間で解く逐次アルゴリズムを与えた.また,O(n/logn)個のプロセッサを用いてO(logn)時間でf-辺彩色問題を解く最適な並列アルゴリズムも与えた.ここでnは入力の大きさである.本アルゴリズムはこれまで知られていなかったものであり重要な成果である.4.2次元平面上にいくつかの障害物および二層配線領域があるときに,指定された2組の端子対を結ぶ2本の道で長さの和が最小なアルゴリズムをO(nlogn)時間,O(n)の記憶量で求めた,ただし,障害物および二層配線領域は軸平行な長方形であるとする.5.平面領域A内でそれぞれの端子対を結ぶ直交線分からなるk本の道で,互いに交差せず,長さの総和が最小なアルゴリズムをO(nlogn)時間で求めた.ここではn=r+kである.ただし,長方形の内部にr個の長方形障害物がある平面領域Aにおいて,k個の端子対が外側の長方形の周および内部の一つの長方形障害物の周にのみあるとする.