next up previous
: 計算時間の比較(多項式=良い,指数関数=悪い) : 近似アルゴリズムでよく取り扱われる問題(代表的なものの一部) : 最大充足割当問題(MAX-SAT)

VLSIレイアウト問題(minimum cut linear arrangement問題)

回路は, 幾つかのチップが配線で結ばれていて, その回路を定規のような 細長い箱に埋め込まなければいけない, つまり, チップを1列に並べて埋め込みたい. そのとき, できるだけ配線が束にならないようにしたいがどの順番でチップを 1列に並べれば良いか? 例えば以下の図の埋め込方では, B,C間(またはC、D間)で3本の 配線が束なっているので, この並べ方では束なりが3である. うまく順番を選ばないと次の図の下図のように束なりが5に なってしまう.



Koichi Yamazaki 平成12年3月15日