抄録
本稿はグラフ埋め込み問題に対する整数計画を提案している.提案手法を用いることにより,任意のゲストグラフとホストグラフに対して,与えられた制約を満たす最適なグラフ埋め込みが求められる.また,複数の評価関数の下で設計点を探索しながら所望のグラフ埋め込みを求める設計方式を提供することができる.いくつかのグラフに対して提案手法を適用した結果についての報告と共に,この整数計画の応用として集積回路(Large Scale Integration:LSI)設計における多端子配線問題に対する整数計画が構成されることが示される.
This paper proposes an integer linear programming (ILP) formulation of the graph embedding problem, which outputs an optimal solution for any pair of guest and host graph. The proposed ILP provides us with a new design style to obtain a desired graph embedding under a variety of metric functions. This paper shows experimental results for several pairs of guest and host graphs, and also shows an ILP formulation of the multi-terminal routing problem in LSI (Large Scale Integration) design as an application of ILP-based graph embedding.
