節点集合の移動に基づく最小コストグラフ分割
スポンサーリンク
概要
- 論文の詳細を見る
VLSIレイアウト設計等の広い応用を持つ最小コストグラフ2分割問題はNP-因難であるため,幾つかのヒューリスティックアルゴリズムが提案されているが,これらの従来手法は一時に1個の節点の移動,もしくは1対の節点の交換により逐次的に初期解を改良していくために局所最適解に陥りやすいという問題点がある.本研究では従来手法におけるこの問題点を解消するために,節点集合の移動に基づくヒューリスティックアルゴリズムを提案し,実験的に評価する.さらに大規模データを高速に処理するために提案アルゴリズムの並列化について考察する.
- 社団法人電子情報通信学会の論文
- 1994-01-26
著者
-
吉田 典可
広島大学工学部第二類(電気系)
-
小出 哲士
広島大学工学部
-
若林 真一
広島大学工学部
-
礒本 和典
マツダ株式会社技術研究所(広島)
-
三政 義康
広島大学工学部
-
吉田 典可
広島大学工学部
関連論文
- 信号経路に対するタイミング制約を考慮した回路分割手法
- タイミング制約を考慮した分割手法
- コンピュータネットワークの活用とその波及効果 : 頭蓋下顎機能障害検査診断システムの試作
- 通信ネットワークの検討 : 通信ネットワーキンググループ
- 通信ネットワークの検討
- ビア数最小化とクロストークを陽に考慮したMCM配線手法
- ビア数最小化とクロストークを陽に考慮したMCM配線手法
- クロストークを考慮したMCM多層配線手法
- 大規模論理回路分割に関する一手法
- 大規模論理回路分割に関する一手法
- 検査・診断データとしてのEMG信号のコンピュータ処理
- セル上配線ネットの選択を同時に行うスタンダードセル方式概略配線アルゴリズム
- タイミング制約を考慮したスタンダードセル概略配線手法
- タイミング制約を考慮したスタンダードセル概略配線手法
- タイミング制約を考慮したスタンダードセル概略配線の一手法
- スタンダードセルレイアウト設計におけるフィードスルー割り当ての一手法
- システムオンシリコン時代を支えるCAD技術(新しい知能化へ向けたLSIシステム技術)
- ネットワークの形状と通信遅延モデルを任意に設定可能な分散アルゴリズムシミュレータ
- 固有の識別子をもたない分散システムにおける耐故障リーダ選挙アルゴリズム
- データベースシステムAIDE-IIIにおけるユーザインタフェースの画面構成
- エンジン制御用リアルタイムソフトウェアに対する要求仕様の記述
- 分散形システムにおけるデッドロックの検出と回復
- クラスタ分割されたネットワークのノード故障対策について
- ゲートマトリックス方式に対するヒューリスティックアルゴリズムの性能評価
- VLSIのブロック配置における矩形重なり除去問題について
- フォームシステムFOSTERにおけるレイアウトの自動調整について
- 3. ハードウェアアルゴリズムの設計法 3.3 シストリック配列とバス付きセル配列上のハードウエアアルゴリズム (VLSI向きハードウェアアルゴリズム)
- 会議スケジュールの自動調整
- VLSI設計におけるチャネルグラフ分割問題について(グラフ理論とその応用)
- グラフの最小コストk分割問題に関する一解法
- PA-2-8 VLSIチップ設計とCADツール
- マルチチップモジュールに対するシステム分割の一手法
- LSI設計の配線におけるグラフの分割(計算機科学の基礎理論)
- 正規集合を受理するパターン・マッチング・マシン(計算機構に関する数学的基礎理論とその応用)
- 交差手法の適応的選択機能を組み込んだ遺伝的アルゴリズムのLSIチップによる実現
- 遺伝的アルゴリズムにおける個体のエリート度に基づく遺伝オペレータとGAパラメータの適応的調整
- 遺伝的アルゴリズムにおける交差手法の適応的選択の一手法
- 適応的交差選択手法を組み込んだ遺伝的アルゴリズムのLSIチップによる実現とその評価
- 個体の優劣度に基づいて適応的にパラメータを調整する遺伝的アルゴリズム
- 遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法
- パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化
- 遺伝的アルゴリズムに対するメタヒューリスティクスに基づくパラメータ値設定手法
- 再配置可能バス付き2次元アレイ上における最近点探索アルゴリズム
- タイミング制約を伴う概略配線問題に対するバッファ挿入と配線幅の選択を許したスタイナ木構成手法
- タイミング制約を考慮した概略配線手法
- BDDサイズを考慮した回路分割に基づく形式的論理検証手法
- BDDサイズを考慮した回路分割に基づく形式的論理検証手法
- 回路分割に基づく組み合わせ回路の形式的検証の一手法
- 寸法制約をもつブロックに対する配置手法
- リアルタイムデータベースシステムにおけるトランザクションの最適スケジューリング
- スタンダードセルレイアウト設計におけるセル配置改良をともなうタイミングドリブン端子割当てアルゴリズム (電子システムの設計技術と設計自動化)
- スタンダードセルレイアウト設計における最適ピン割当て
- ATMネットワークにおける複数のQoSクラスを考慮したVPトポロジ設計と帯域幅割当て手法
- 層割当てに基づくタイミングとクロストークを考慮したMCM配線手法
- データパスレイアウトにおける機能ブロック配置の一手法
- データパスレイアウトのための分枝限定法に基づくフロアプランアルゴリズム
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- 動的ネットワークにおける経路更新問題を解く分散アルゴリズム
- ネットワーク下位プロトコルを考慮した分散アルゴリズムシミュレータ
- 動的ネットワークにおける最短経路木更新問題を解く分散アルゴリズム
- タイミング制約を考慮した非線形計画に基づくスタンダードセル配置手法
- タイミング制約とレジスタ配置を陽に考慮したセル配置手法
- VLSIによる実現に適したグラフ2分割並列アルゴリズム
- グラフを2分割するハードウェアアルゴリズム
- 節点集合の移動に基づく最小コストグラフ分割
- 節点集合の移動に基づくグラフ分割手法
- 最小生成木構成問題を解く自己安定分散アルゴリズム
- 複数行にわたるブロックを考慮したセル敷き詰め型ゲートアレイの配置手法
- 大規模回路の最小コスト分割のための分散遺伝的アルゴリズム
- 複数チャネルの配線を考慮したセルモデルに対する3層セル上チャネル配線手法
- セル上でのビアを許したセル上チャネル配線の一手法
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- Pセンタ問題およびデータ変換に関連した問題の計算複雑さ (計算の複雑性に関する研究)
- 遺伝的アルゴリズムの高速実行に適した命令セットを持つRISCプロセッサDLX-GA
- ハイパーグラフ分割のための動的クラスタリングに基づくヒューリスティックアルゴリズム
- ハイパーグラフ分割のための動的クラスタリングに基づくヒューリスティックアルゴリズム
- 動的クラスタリングに基づくハイパーグラフk分割手法
- ハイパーグラフk分割手法に基づくスタンダードセル配置手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- 大規模回路に対するタイミングドリブン多層概略配線の一手法
- VLSIフロアプランニングにおける端子位置決定問題について
- MCM設計のためのパフォーマンスと物理的制約を考慮した回路分割手法
- 制約グラフに基づくフロアプラン設計の一手法
- グラフを〓分割する並列アルゴリズム
- 階層構造をもたせたネットに対する概略配線手法
- 構造的モデルを用いた論理回路図の自動描画について
- フォーム言語のためのソフトウェア開発支援システム
- ブロック間の相対位置制約の操作に基づくビルディングブロックフロアプラン設計手法
- 論理回路分割と線形計画法に基づく階層的スタンダードセル配置手法
- 任意時刻のプロセスの故障と復帰を考慮した分散相互排除アルゴリズム
- 複数プロセス故障を許した耐故障分散相互排除アルゴリズム(計算モデルと計算の複雑さに関する研究)
- パフォーマンスを考慮したアナログLSIモジュールジェネレータ
- 配線の寄生素子を考慮したアナログLSI配置手法
- 各信号経路においてカットされるネット数に制約を持つ大規模回路分割手法
- 各信号経路においてカットされるネット数に制約を持つ大規模回路分割手法