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

Takagi Kazuyoshi, Takagi Naofumi, Yajima Shuzo

最小カット線形配置問題は、グラフの節点の線形配列のうち、枝の重なりの最大値が最小のものを求める問題である。木に対しては、この問題を解く多項式時間アルゴリズムが知られているが、一般のグラフに対しては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.

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

Bibliographic Information

Search this article

Description

Journal

Keywords

Details 詳細情報について

Export

Report a problem