| 講演名 | 1996/7/26 矩形パッキングのための最大重み減少列を求めるアルゴリズム 高橋 俊彦, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitaniにより,矩形パッキング問題における画期的な許容解の表現力法が提案された.この表現方法はSEQ-PAIRと呼ばれ,効率のよい解の探索を可能にし,アルゴリズムの計算時間を飛躍的に向上させた.本報告では重みつきの順列における最大重み減少列を求める問題に対し,効率的アルゴリズムを提案すると同時に,このアルゴリズムをSEQ-PAIRを用いたパッキングアルゴリズムに採用することで,さらに計算時間を減らすことができることを示した.アルゴリズムの計算量はO(nω)であるが,データ構造を工夫することでO(n log n)となる(ただし,ωは最大重み減少列の長さ). |
| 抄録(英) | H. Murata, K. Fbjiyoshi, S. Nakatake, and Y. Kajitani introduced a epoch-making coding scheme for feasible solutions of rectangle packing problem. This scheme is called SEQ-PAIR and highly improved the computational time. We present an algorithm for finding a maximum-weight decreasing sequence in a permutation and show its effectivity for the rectangle packing algorithm.The time complexity of the algorithm presented in this report is O(nω), where ω is the weight of the maximum weight decreasing sequence. However, we can get O(n log n)-time algorithm on adopting balanced tree for its data structure. This algorithm is also the fastest one for finding maximum weighted clique in a weighted permutation graph. |
| キーワード(和) | 矩形パッキング / SEQ-PAIR / permutation graph |
| キーワード(英) | rectangle packing / SEQ-PAIR / permutation graph / maximum weight clique |
| 資料番号 | VLD96-30 |
| 発行日 |
| 研究会情報 | |
| 研究会 | VLD |
|---|---|
| 開催期間 | 1996/7/26(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | VLSI Design Technologies (VLD) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 矩形パッキングのための最大重み減少列を求めるアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Finding a Maximum-Weight Decreasing Sequence in a Permutation, Motivated by Rectangle Packing Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 矩形パッキング / rectangle packing |
| キーワード(2)（和/英） | SEQ-PAIR / SEQ-PAIR |
| キーワード(3)（和/英） | permutation graph / permutation graph |
| 第 1 著者 氏名（和/英） | 高橋 俊彦 / Toshihiko Takahashi |
| 第 1 著者 所属（和/英） | 新潟大学大学院自然科学研究科 Graduate School of Science and Technology Niigata University |
| 発表年月日 | 1996/7/26 |
| 資料番号 | VLD96-30 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 201 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |