有向非巡回グラフの線形配置アルゴリズムについて

高木 一義, 高木 直史, 矢島 脩三

最小カット線形配置問題は、グラフの節点の線形配列のうち、枝の重なりの最大値が最小のものを求める問題である。木に対しては、この問題を解く多項式時間アルゴリズムが知られているが、一般のグラフに対してはNP-完全である。本稿では、完全p-q dagに対する最小カット線形配置問題のアルゴリズムを二つ提案する。p-q dagは、有向非巡回グラフの一つのクラスであり、ある種の繰り返し構造を持つ回路の結合網として用いられる。第一のアルゴリズムは、動的計画法に基づくものであり、グラフのサイズに対して多項式オーダの計算時間と計算領域を要する。第二のアルゴリズムは、線形配置の性質に基づく近似アルゴリズムである。最後に、これらのアルゴリズムの応用として、多オペランド加算器の組織的なVLSIレイアウト手法を示す。
The minimum cut linear arrangement problem of a graph is the problem to find a vertex ordering which minimizes the maximum edge congestion.Although this problem can be solved in polynomial time for trees,NP-complete in general. In this paper,we present two algorithms for minimum cut linear arrangement of complete p-q dags.p-q dags are a class of directed acyclic graphs often used as interconnection scheme of a class of iterative circuits. The first algorithm is based on dynamic programming.It requires time and space polynomial in the size of a given graph.The other algorithm is an approximation algorithm which ensures solution within a constant factor of the minimum. We present a systematic VLSI layout method of multiple operand adders as an application of the algorithms.

有向非巡回グラフの線形配置アルゴリズムについて

書誌事項

この論文をさがす

説明

収録刊行物

キーワード

詳細情報詳細情報について

書き出し

問題の指摘

有向非巡回グラフの線形配置アルゴリズムについて

書誌事項

この論文をさがす

説明

収録刊行物

キーワード

詳細情報 詳細情報について

書き出し

問題の指摘

詳細情報詳細情報について