整数計画法によるグラフ埋め込みの定式化とLSI配線への応用

摘要

本稿はグラフ埋め込み問題に対する整数計画を提案している．提案手法を用いることにより，任意のゲストグラフとホストグラフに対して，与えられた制約を満たす最適なグラフ埋め込みが求められる．また，複数の評価関数の下で設計点を探索しながら所望のグラフ埋め込みを求める設計方式を提供することができる．いくつかのグラフに対して提案手法を適用した結果についての報告と共に，この整数計画の応用として集積回路(Large Scale Integration: LSI)設計における多端子配線問題に対する整数計画が構成されることが示される．