グラフの最小コストk分割問題に関する一解法
スポンサーリンク
概要
- 論文の詳細を見る
本稿では枝に重みを持つ無向グラフ G=(V,E)と整数 k(≥2)が与えられたとき, グラフをK個の部分グラフに分割する最小コスト分割を求める多項式アルゴリズムを提案する. |V|=nとしたとき, 提案アルゴリズムは O(n^<2(k-2)>)回の最大流-最小コストカットアルゴリズムを適用する. 提案手法では最小コストk分割のコストのある定数倍以下のコストを持つ全ての2分割を列挙ことにより最小コストk分割を求める. 従来手法として Golschmidtらによる偶数Kに対しては O(n^<k^2-3k/2+2>),奇数kに対しては O(n^<k^2-3k/2+5/2>)の計算時間を持つアルゴリズムが挙げられる.
- 1997-06-20
著者
-
上土井 陽子
広島市立大学 情報科学部 情報工学科
-
若林 真一
広島大学工学部
-
吉田 典可
広島市立大学情報科学部
-
吉田 典可
広島市立大学大学院 情報科学研究科
-
吉田 典可
広島市立大学大学院情報科学研究科情報工学専攻
関連論文
- マイクロコンピュータ設計教育環境City-1 : FPGAコンピュータの自由な設計と製作
- 信号経路に対するタイミング制約を考慮した回路分割手法
- タイミング制約を考慮した分割手法
- ビア数最小化とクロストークを陽に考慮したMCM配線手法
- ビア数最小化とクロストークを陽に考慮したMCM配線手法
- クロストークを考慮したMCM多層配線手法
- 非公開データベース間における機密性の高い情報共有の検討
- コールアドミッションアルゴリズムに適した経路探索法の提案
- A-1-30 コールアドミッションに適した効率的な経路探索法の提案(A-1.回路とシステム,一般講演)
- 分散処理環境でのオンラインルーティング・スケジューリング手法の実験的考察
- 分散処理環境でのオンラインルーティング・スケジューリング手法の実験的考察
- 負荷分散問題に対するオンライン・アルゴリズム
- 分散処理環境での負荷分散問題に対するオンラインスケジューリング手法の実験的考察
- クラスタリング結果の特徴抽出を用いる高次元データの対話的クラスタリング
- FlexDice: 高次元な大規模データセットに対する高速クラスタリング手法
- 最小コストκ分割を全て求めるアルゴリズム
- 多次元データ空間に対する高速クラスタリングと実験的評価
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- トラフィックの変動に関するコールアドミッションアルゴリズムの性能影響解析
- A-31 演算の対象となるデータに注目したアルゴリズム実行中の消費電力削減手法(計算モデル,A.アルゴリズム・基礎)
- A-26 データの事前圧縮によるソートアルゴリズムの高速化に関する考察(離散アルゴリズム(3),A.アルゴリズム・基礎)
- M-22 入力系列パターンに着目したコールアドミッションアルゴリズムの実験的性能解析(サービス・資源管理と応用(2),M.ネットワーク・モバイルコンピューティング)
- D-39 不均一サイズセルを用いた階層的クラスタリングの高速化(データマイニング,D.データベース)
- 共有オブジェクト上での競合低減を目的とする非同期分散合意手法の提案
- 大規模論理回路分割に関する一手法
- 大規模論理回路分割に関する一手法
- セル上配線ネットの選択を同時に行うスタンダードセル方式概略配線アルゴリズム
- タイミング制約を考慮したスタンダードセル概略配線手法
- タイミング制約を考慮したスタンダードセル概略配線手法
- タイミング制約を考慮したスタンダードセル概略配線の一手法
- スタンダードセルレイアウト設計におけるフィードスルー割り当ての一手法
- システムオンシリコン時代を支えるCAD技術(新しい知能化へ向けたLSIシステム技術)
- ネットワークの形状と通信遅延モデルを任意に設定可能な分散アルゴリズムシミュレータ
- 固有の識別子をもたない分散システムにおける耐故障リーダ選挙アルゴリズム
- グラフの最小コストk分割問題に関する一解法
- マルチチップモジュールに対するシステム分割の一手法
- 共有変数へのアクセス競合の回避を目的とする同時実行可能で拡張可能なハッシュアルゴリズムの改良
- LSI設計の配線におけるグラフの分割(計算機科学の基礎理論)
- 正規集合を受理するパターン・マッチング・マシン(計算機構に関する数学的基礎理論とその応用)
- 交差手法の適応的選択機能を組み込んだ遺伝的アルゴリズムのLSIチップによる実現
- 遺伝的アルゴリズムにおける個体のエリート度に基づく遺伝オペレータとGAパラメータの適応的調整
- 遺伝的アルゴリズムにおける交差手法の適応的選択の一手法
- 適応的交差選択手法を組み込んだ遺伝的アルゴリズムのLSIチップによる実現とその評価
- 個体の優劣度に基づいて適応的にパラメータを調整する遺伝的アルゴリズム
- 遺伝的アルゴリズムにおける個体の優劣度に基づく適応的パラメータ値設定手法
- パラメータの適応的調整を伴う遺伝的アルゴリズムのハードウェア化
- 遺伝的アルゴリズムに対するメタヒューリスティクスに基づくパラメータ値設定手法
- 再配置可能バス付き2次元アレイ上における最近点探索アルゴリズム
- タイミング制約を伴う概略配線問題に対するバッファ挿入と配線幅の選択を許したスタイナ木構成手法
- タイミング制約を考慮した概略配線手法
- BDDサイズを考慮した回路分割に基づく形式的論理検証手法
- BDDサイズを考慮した回路分割に基づく形式的論理検証手法
- 回路分割に基づく組み合わせ回路の形式的検証の一手法
- リアルタイムデータベースシステムにおけるトランザクションの最適スケジューリング
- スタンダードセルレイアウト設計におけるセル配置改良をともなうタイミングドリブン端子割当てアルゴリズム (電子システムの設計技術と設計自動化)
- スタンダードセルレイアウト設計における最適ピン割当て
- 匿名データ収集におけるプロトコルからの逸脱防止法の効率化(一般(ストリーム・匿名性・省電力),e-ScienceとData Intensive Science及び一般)
- ATMネットワークにおける複数のQoSクラスを考慮したVPトポロジ設計と帯域幅割当て手法
- 層割当てに基づくタイミングとクロストークを考慮したMCM配線手法
- データパスレイアウトにおける機能ブロック配置の一手法
- データパスレイアウトのための分枝限定法に基づくフロアプランアルゴリズム
- グラフの最小コスト部分分割について
- 共有情報を用いた同時実行可能なゼロ知識識認証について(セッション1)
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- 非線形計画法に基づく並列タイミングドリブンスタンダードセル配置手法
- 動的ネットワークにおける経路更新問題を解く分散アルゴリズム
- ネットワーク下位プロトコルを考慮した分散アルゴリズムシミュレータ
- 動的ネットワークにおける最短経路木更新問題を解く分散アルゴリズム
- タイミング制約を考慮した非線形計画に基づくスタンダードセル配置手法
- タイミング制約とレジスタ配置を陽に考慮したセル配置手法
- VLSIによる実現に適したグラフ2分割並列アルゴリズム
- グラフを2分割するハードウェアアルゴリズム
- 節点集合の移動に基づく最小コストグラフ分割
- 節点集合の移動に基づくグラフ分割手法
- 最小生成木構成問題を解く自己安定分散アルゴリズム
- 複数行にわたるブロックを考慮したセル敷き詰め型ゲートアレイの配置手法
- 大規模回路の最小コスト分割のための分散遺伝的アルゴリズム
- 複数チャネルの配線を考慮したセルモデルに対する3層セル上チャネル配線手法
- セル上でのビアを許したセル上チャネル配線の一手法
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- バッファ挿入を考慮した概略配線とフロアプランを同時に求めるフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- 適応的遺伝的アルゴリズムとシーケンスペアに基づくフロアプランニング手法
- Pセンタ問題およびデータ変換に関連した問題の計算複雑さ (計算の複雑性に関する研究)
- 遺伝パラメータの適応的調整機能をもつ並列遺伝的アルゴリズム
- 遺伝的アルゴリズムの高速実行に適した命令セットを持つRISCプロセッサDLX-GA
- ハイパーグラフ分割のための動的クラスタリングに基づくヒューリスティックアルゴリズム
- ハイパーグラフ分割のための動的クラスタリングに基づくヒューリスティックアルゴリズム
- 動的クラスタリングに基づくハイパーグラフk分割手法
- ハイパーグラフk分割手法に基づくスタンダードセル配置手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- ULSI多層配線に対するバッファ挿入と配線幅を考慮したタイミングドリブン階層概略配線手法
- 大規模回路に対するタイミングドリブン多層概略配線の一手法
- VLSIフロアプランニングにおける端子位置決定問題について
- MCM設計のためのパフォーマンスと物理的制約を考慮した回路分割手法
- 制約グラフに基づくフロアプラン設計の一手法
- グラフを〓分割する並列アルゴリズム
- 生態ピラミッドの概念を取り入れた遺伝的アルゴリズムの提案(アルゴリズムと計算量理論)
- 論理回路分割と線形計画法に基づく階層的スタンダードセル配置手法