- 著者
-
高木 一義
高木 直史
矢島 脩三
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.93, no.81, pp.85-92, 1993-05-27
最小カット線形配置問題は、グラフの節点の線形配列のうち、枝の重なりの最大値が最小のものを求める問題である。木に対しては、この問題を解く多項式時間アルゴリズムが知られているが、一般のグラフに対してはNP-完全である。本稿では、完全p-q dagに対する最小カット線形配置問題のアルゴリズムを二つ提案する。p-q dagは、有向非巡回グラフの一つのクラスであり、ある種の繰り返し構造を持つ回路の結合網として用いられる。第一のアルゴリズムは、動的計画法に基づくものであり、グラフのサイズに対して多項式オーダの計算時間と計算領域を要する。第二のアルゴリズムは、線形配置の性質に基づく近似アルゴリズムである。最後に、これらのアルゴリズムの応用として、多オペランド加算器の組織的なVLSIレイアウト手法を示す。