講演名 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
発行日