| 講演名 | 1993/5/27 有向非巡回グラフの線形配置アルゴリズムについて 高木 一義, 高木 直史, 矢島 脩三, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 最小カット線形配置問題は、グラフの節点の線形配列のうち、枝の重なりの最大値が最小のものを求める問題である。木に対しては、この問題を解く多項式時間アルゴリズムが知られているが、一般のグラフに対しては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. |
| キーワード(和) | グラフ / 線形配置問題 / 多項式時間アルゴリズム / VLSIレイアウト |
| キーワード(英) | graph / linear arrangement problem / polynomial time algorithm / VLSI layout |
| 資料番号 | COMP93-18,SS93-12 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1993/5/27(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | 有向非巡回グラフの線形配置アルゴリズムについて |
| サブタイトル（和） | |
| タイトル（英） | On Linear Arrangement Algorithms for Directed Acyclic Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 線形配置問題 / linear arrangement problem |
| キーワード(3)（和/英） | 多項式時間アルゴリズム / polynomial time algorithm |
| キーワード(4)（和/英） | VLSIレイアウト / VLSI layout |
| 第 1 著者 氏名（和/英） | 高木 一義 / Kazuyoshi Takagi |
| 第 1 著者 所属（和/英） | 京都大学工学部情報工学教室 Faculty of Engineering,Kyoto University |
| 第 2 著者 氏名（和/英） | 高木 直史 / Naofumi Takagi |
| 第 2 著者 所属（和/英） | 京都大学工学部情報工学教室 Faculty of Engineering,Kyoto University |
| 第 3 著者 氏名（和/英） | 矢島 脩三 / Shuzo Yajima |
| 第 3 著者 所属（和/英） | 京都大学工学部情報工学教室 Faculty of Engineering,Kyoto University |
| 発表年月日 | 1993/5/27 |
| 資料番号 | COMP93-18,SS93-12 |
| 巻番号（vol） | vol.93 |
| 号番号（no） | 81 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |