3次元VLSI設計並列アルゴリズムに関する研究

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

3次元VLSI設計に関して種々の理論的観点から調査・検討を行い,問題点を明らかにした。更に並列配線アルゴリズムの理論的基礎を与え,そのプロトタイプを設計し,理論的に解析した。1.VLSIの一般配線問題は平面(格子)グラフで点素な道を求める問題として定式化できる。配線領域を表す平面グラフG及び同電位にしたい端子対の集合(既ちネット)がいくつか与えられたとき,各ネットの端子を連結する道で互いに点素なものを求めたい。本研究ではネットの端子が平面グラフGに3つの面上にだけ置かれていて,各端子対の2つの端子が同じ面上にある場合に対し,Gに点素な道がある限りそれらを具体的に求める線形時間アルゴリズムを与えた。2.与えられた凸m角形内部のすべての整数格子点を列挙するO(K+m+logn)時間のアルゴリズムを与えた。ここでKは列挙された格子点の個数であり,nは凸m角形の大きさ,すなわちm角形を包含する軸平行な長方形の垂直,水平な辺のうち短い方の長さである。さらに,m個の制約式を持つ2変数整数計画問題を解くO(mlogm+logn)時間のアルゴリズムを与えた。ここでnは計画問題の許容解空間である凸多角形の大きさを表す。このアルゴリズムは従来知られているアルゴリズムより単純であり,時間計算量も改善している。3.グラフG=(V,E)のf辺彩色とは同じ色の辺が各点での接続辺中に高々f(v)本しか存在しないようにGの全ての辺を彩色することである。そのために必要な最小の色数はX'_f(G)と書かれる。X'_f(G)【less than or equal】max{「(d(v)+p(vw))/f(v)」:v,w∈V}であることは従来から知られていた。ここでd(v)は点vの次数,P(vw)は点v,w間の多重辺数である。本研究では上式右辺の色数でグラフGをf辺彩色する効率のよいアルゴリズムを与えた。その計算時間はO(|E|△_flog|E|)あるいはO(|E|√|E|log|E|)である。