電子情報通信学会総合大会講演要旨
D-1-2
疎な1対1ネットに対する3次元チャネル配線アルゴリズム
○益子隆広・山田敏規(埼玉大)
3次元チャネルとは3次元格子Gであり, その列, 行, 層は, x-, y-, z-座標を固定して定義される. 層の数をGの高さと呼ぶ.1対1ネットは三次元チャネルの繋がれるべき頂点(端子) を2つ含む. ネット内の端子を繋ぐ木(スタイナー木)を配線と呼ぶ. 3次元1対1チャネル配線問題とは, 異なる1対1ネットに対する配線が互いに素になるような方法で, できるだけ少ない層で, 各ネットに対して配線を与える問題であり, NP-困難であることが知られている. 小文ではネットの数がRC個, 各層が2R✕2Cの2次元格子である3次元1対1チャネル配線問題に対して, 高さO(R+C)で配線可能であることを示す.