直交順序を保存する方形の最小面積非交差再配置問題
スポンサーリンク
概要
- 論文の詳細を見る
あらかじめ平面上に配置されているn個の方形の集合に対して, 直交順序を保存し, 方形同士が交差しない, という制約のもとで, 面積最小の再配置を求める問題について考察する. 三末らはこの問題に対し, O(n^2)時間の発見的アルゴリズムを提案した. 本論文ではまず, ある面積以下で再配置可能かどうかを判定する問題が, NP完全であることを証明する. 更に, 面積最小の再配置を求めるO(n^2)時間の発見的再配置アルゴリズムを与え, このアルゴリズムで得られる再配置面積が, 三末らの手法で得られる面積以下であることを証明する. また, ランダムな初期配置に対して計算機実験を行い, 特に方形数が多い場合に, 三末らの結果に比べて15〜20%の面積で再配置できることを示す.
- 社団法人電子情報通信学会の論文
- 1999-06-25
著者
-
藤原 秀雄
奈良先端科学技術大学院大学 情報科学研究科
-
井上 美智子
奈良先端科学技術大学院大学情報科学研究科
-
林 邦彦
奈良先端科学技術大学院大学情報科学研究科:(現)松下電器産業株式会社
-
増澤 利光
奈良先端科学技術大学院大学情報科学研究科
-
井上 美智子
奈良先端科学技術大学院大学
-
井上 美智子
奈良先端科学技術大学院大学 情報科学研究科:科学技術振興機構crest
-
井上 美智子
奈良先端科学技大学院大学
関連論文
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (コンカレント工学)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (信号処理)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (VLSI設計技術)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について (回路とシステム)
- 部分スルー可検査性に基づく順序回路のテスト生成法(ディペンダブルコンピューティング)
- 共有メモリシステムにおける調停木スキップ相互排除アルゴリズム
- マルチクロック・ドメイン・コアテストのための再構成可能ラッパーの一構成法(テスト容易化設計,デザインガイア2008-VLSI設計の新しい大地)
- マルチクロック・ドメイン・コアテストのための再構成可能ラッパーの一構成法(テスト容易化設計,デザインガイア2008-VLSI設計の新しい大地-)
- セキュアスキャン設計のためのシフトレジスタ等価回路の列挙と合成
- 内蔵プロセッサを利用したマイクロコントローラのテスト高速化に関する考察
- BISTにおける高品質遅延故障テストのためのシード選択法(遅延故障テスト,VLSI設計とテスト及び一般)
- セキュアスキャン設計のためのシフトレジスタ等価回路の列挙と合成(ディペンダブルコンピューティング)
- マルチクロック・ドメイン・コアテストのための再構成可能ラッパーの一構成法(テスト容易化設計,デザインガイア2008-VLSI設計の新しい大地)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について(システムと信号処理及び一般)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について(システムと信号処理及び一般)
- CAS2010-6 セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について(システムと信号処理及び一般)
- セキュアスキャン設計におけるシフトレジスタ等価回路の微分動作同値類について(システムと信号処理及び一般)
- C素子スキャンパスを用いた非同期式順序回路に対する完全スキャン設計法(設計/テスト/検証)
- AI-1-7 フィールド高信頼化のための回路・システム機構(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- 状態並列に基づく順序回路テスト生成の並列処理について
- 安定後の1故障を考慮したリングでの自己安定相互排除プロトコル
- 安定後の1故障を考慮したリングでの自己安定相互排除プロトコル
- 直交順序を保存する方形の最小面積非交差再配置問題
- 直交順序を保存する矩形の非交差再配置問題について
- 動作記述を用いた順序テスト生成およびテスト容易化バインディング(高位設計2,デザインガイア2010-VLSI設計の新しい大地-)
- 動作記述を用いた順序テスト生成およびテスト容易化バインディング(高位設計2,デザインガイア2010-VLSI設計の新しい大地-)
- 非パイプラインプロセッサの命令レベル自己テストのためのテスト容易化設計(上流DFT,VLSI設計とテスト及び一般)
- 縮退故障とパス遅延故障のためのプロセッサの命令レベル自己テスト法(LSIのテスト・診断技術論文)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- パイプラインプロセッサ自己テストのための命令テンプレート生成(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- プロセッサ自己テストのためのコントローラ入力時相空間制約(VLSI設計とテスト)
- データフローを考慮したプロセッサ自己テストのためのテンプレート生成(VLSI設計とテスト)
- 分散移動システムにおけるスナップショット・アルゴリズム
- SREEP : SR等価回路を用いたセキュアスキャン設計支援ツール(テスト設計2,デザインガイア2010-VLSI設計の新しい大地-)
- SREEP : SR等価回路を用いたセキュアスキャン設計支援ツール(テスト設計2,デザインガイア2010-VLSI設計の新しい大地-)
- BISTの故障を考慮した故障検出率と市場不良率の関係(ディペンダブルソフトウェアとネットワーク及び一般)
- PD-3-5 組合せテスト生成複雑度と非スキャンテスト容易化設計法
- 選択問題を解くBSPモデル及びBSP^*モデル上の並列アルゴリズム
- 2値画像上の全最近点を求めるBSPモデル上の並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム
- CGMモデル及びBSPモデル上で選択及びソートを行う並列アルゴリズム(並列・分散)
- 選択問題を解くBSPモデルおよびBSPモデル上の並列アルゴリズム
- 故障推定機能を利用した永久故障に耐性のある自己安定プロトコル
- テスト実行時の温度均一化のためのテストパターン並び替え法(Iddqテスト・温度均一化,VLSI設計とテスト及び一般)
- 無閉路部分スキャン設計に基づくデータパスのテスト容易化高位合成におけるバインディング手法
- 無閉路部分スキャン設計を指向したデータパスのテスト容易化高位合成
- 内部平衡構造に基づく部分スキャン設計法に関する考察
- 組合せテスト生成複雑度でテスト生成可能な順序回路構造とその応用
- 組合せテスト生成可能な拡張部分スキャン設計
- 組合せテスト生成複雑度でテスト生成可能な順序回路
- 時間展開モデルを用いた無閉路順序回路のテスト系列圧縮方法 (テストと設計検証論文特集)
- 時間展開モデルを用いた無閉鎖順序回路のテスト系列圧縮について
- 時間展開モデルを用いた無閉路順序回路のテスト系列圧縮について
- 時間展開モデルを用いた無閉鎖順序回路のテスト系列圧縮について
- 木ネットワーク上のヒープ順序構成自己安定プロトコル
- 木ネットワークでヒープ順序を実現する自己安定プロトコル (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- ヒープ順序づき木を構成する自己安定プロトコル
- メモリコアに対する組込み自己修復を考慮したSoCのテストスケジューリング(デザインガアイ2006-VLSI設計の新しい大地を考える研究会)
- メモリコアに対する組込み自己修復を考慮したSoCのテストスケジューリング(VLSIのテストII,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- メモリコアに対する組込み自己修復を考慮したSoCのテストスケジューリング(VLSIのテストII,デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- メモリコアに対する組込み自己修復を考慮したSoCのテストスケジューリング
- 消費電力を考慮したマルチクロックドメイン SoC のテストスケジューリング(スケジューリング, VLSI 設計とテスト及び一般)
- テスト長制約下での欠陥検出率向上のための状態可観測なFSMのテスト生成法(上流テスト・テスト圧縮,VLSI設計とテスト及び一般)
- 状態可観測なFSMの故障非依存/依存テスト生成法(上流DFT,VLSI設計とテスト及び一般)
- テーブル参照型FPGAにおける論理ブロックの検査法
- テーブル参照型FPGAのテスト
- 完全故障検出効率を保証するRTLデータパスの部分強可検査性に基づくテスト容易化設計法(半導体テスト,ディペンダブルコンピューティング論文)
- 完全故障検出効率を保証するデータパスの部分強可検査設計
- 完全故障検出効率を保証するデータパスの部分強可検査設計(上流 DFT, VLSI 設計とテスト及び一般)
- セキュアスキャン設計のためのシフトレジスタ等価回路の列挙と合成について(安全性及び一般)
- RTLパス数最小化のためのリソースバインディング法(スキャンテスト・テスト容易化高位合成,VLSI設計とテスト及び一般)
- 2値画像の重みつき距離変換を行なう並列アルゴリズム
- 無閉路可検査順序回路のクラス拡張に関する考察(セッション4 : オーバテストとテスト生成複雑度, VLSI設計とテスト及び一般)
- 消費電力を考慮したマルチクロックドメインコアに対する再構成可能ラッパー設計(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 消費電力を考慮したマルチクロックドメインコアに対する再構成可能ラッパー設計(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 消費電力を考慮したマルチクロックドメインコアに対する再構成可能ラッパー設計(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 消費電力を考慮したマルチクロックドメインコアに対する再構成可能ラッパー設計(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 再構成可能結合ラッパーを用いた SoC のテストスケジューリング(スケジューリング, VLSI 設計とテスト及び一般)
- 同位相構造に基づく特定用途を考慮したFPGA相互接続遅延テスト(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 同位相構造に基づく特定用途を考慮したFPGA相互接続遅延テスト(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 同位相構造に基づく特定用途を考慮したFPGA相互接続遅延テスト(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 同位相構造に基づく特定用途を考慮したFPGA相互接続遅延テスト(VLSIの設計/検証/テスト及び一般(デザインガイア))
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 単一端子変化遅延テストに基づくデータパスのテスト容易化設計(テスト設計)(VLSIの設計/検証/テスト及び一般)(デザインガイア2004-VLSI設計の新しい大地を考える研究会-)
- 非同期共有メモリシステムにおける適応型繰り返し改名アルゴリズム
- レジスタ転送レベルデータパスの単一制御並行可検査性に基づく組込み自己テスト法
- 演算器の強可検査性を保証するテスト容易化高位合成
- 固定制御可検査性に基づくRTL回路の非スキャンテスト容易化設計法
- レジスタ転送レベルデータパスの単一制御並行可検査性に基づく組込み自己テストについて
- レジスタ転送レベルデータパスの単一制御並行可検査性に基づく組込み自己テストについて
- レジスタ転送レベルデータパスの単一制御可検査性に基づく組込み自己テスト容易化設計法
- 強可検査性に基づくテスト容易化高位合成
- 強可検査性に基づくテスト容易化高位合成
- 強可検査性に基づくテスト容易化高位合成