枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
技重み付き一般構造グラフの最大マッチングの下限は点数nが偶数のとき(ω(E))/((n-1))、奇数のとき(ω(E)-ω(I_υ)/(n-2))であることを示す。但し、ω(E)は技重み総和であり、ω(I_υ)は最小の接続枝重み和である。証明は最大マッチングが性質4CYCLEを満たすことを用いる解析的な方法と線形アルゴリズムで構成する方法の二通りで示す。ここで4CYCLEとは、長さ4の交互サイクル上の変換でマッチング重み和が増大しないという性質である。後者で構成されるマッチングは必ずしも4CYCLEを満たさない。
- 一般社団法人情報処理学会の論文
- 1995-05-12
著者
-
梶谷 洋司
東京工業大学工学部電気・電子工学科
-
藤吉 邦洋
北陸先端科学技術大学院大学情報科学研究科
-
梶谷 洋司
東京工業大学 大学院 理工学研究科 集積システム専攻
-
Cho Jun
Sung Kyun Kwan Univ., Korea
-
Sarrafzadeh Majid
Northwestern-Univ., USA
-
Cho Jun
Sungkyunkwan Univ. Suwon Kor
-
Cho Jun
Sung Kyun Kwan Univ. Korea
-
Sarrafzadeh Majid
Northwestern-univ. Usa
関連論文
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- Flipにより自己変換するスタイナ木とそのVLSI最適配線への応用(電子システムの設計技術と設計自動化)
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Elip
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- アナログ集積回路での共通重心に対応した配置手法に関する研究(物理設計,物理設計及び一般)
- VISI回路の階層設計をサポートする階層化BSGフロアプラン
- 確率的探索手法に基づく凸多角形パッキング手法の提案
- 抽象データ構造による高密度3次元パッキング手法
- 複数ネットの非交差配線における探索的最適化手法の提案
- 複数ネットの非交差配線における探索的最適化手法の提案
- 最適配線レイアウトの為のスタイナー木生成手法Flip
- 凸型矩形を扱うMultiple-BSG配置手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- BSG構造に基づく配置・概略配線同時最適化手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- 座標固定モジュールを扱うBSG構造におけるモジュール配置手法の考案
- 相似拡大モデルに基づき配線領域を確保したモジュール配置手法の提案
- モジュール配置問題を解く限定スライス構造の提案
- モジュール配置問題を解く限定スライス構造の提案
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式回路におけるスケジュールクロック木の構成
- 準同期式におけるクロック配線駆動配置
- 準同期式におけるクロック配線駆動配置
- 端子間容量行列の枝容量和最小実現の枝数最小化について(グラフ理論とその応用)
- 最小数枝付加によるk-枝連結グラフの(k+1)-枝連結グラフへの拡大構成(グラフ理論とその応用)
- 3-消去可能グラフについて(グラフ理論とその応用)
- 回路分割のためのビンパッキングアルゴリズムFFDとその拡張
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 一般構造フロアプランの面積最小化のための疑似気圧モデルと高速アルゴリズム
- 容量を固定した整数ビンパッキング問題のFFD法による解法
- ビンの容量を制限したキューブパッキング問題のNP完全性について
- 二つのグラフの共通木グラフについて(グラフ理論とその応用)
- 枝重み付き一般グラフの最大マッチングの下限と線形時間近似アルゴリズム
- 多端子ネットの2端子ネット集合へのビア数に関する等価変換
- 多層多端子位相配線におけるネット当りのビア数について
- 2端子ネットビア数最小化問題の区間分割に関する動的計画法による解法
- 多層多端子ネットの位相配線におけるビア数最小化問題について
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- モジュールの重なりを許さない力学的モデルによるモジュール配置手法の提案
- A-3-4 局所方向性を持つFPGAの経由スイッチ数最小化配置アルゴリズム
- Suppression of Edge Effects Based on Analytic Model for Leakage Current Reduction of Sub-40nm DRAM Device
- フロアプランの部屋間チャネル隣接を表現するHalf-State Sequence(H-Seq)
- パラメトリックBSGによるレイアウトデザインの再利用
- パラメトリックBSGによるレイアウトデザインの再利用
- A-3-1 近接度に着目した入出力ピン配置アルゴリズム
- COMP2000-17 壁と部屋に関する位相方形分割のReduct-Seqによる数え上げ
- Reduct-Seq表現による高速な一般構造フロアプラニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプランニング
- CAS2000-15 / VLD2000-24 / DSP2000-36 Reduct-Seq表現による高速な一般構造フロアプラニング
- クリティカルパスのリビジットに着目した回路分割遅延改善手法の提案
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 最小カットを用いて適切な部分回路を抽出するための効率的手法
- 疑似気圧モデルに基づくVLSIフロアプランの局所修正
- 疑似気圧モデルに基づくVLSIフロアプランの局所修正
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- マルチプロセッサの低消費電力化のためのクロックON/OFFスケジューリング
- 最大フロー手法を応用した論理回路モデルグラフの最小カット列挙法と回路分割手法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- 準同期式回路の実現に適したクロック木構成法
- リソース制約付き回路分割問題に関する一考察
- 線長の総和と最大に関する均衡平面スタイナー木
- 線長の総和と最大に関する均衡平面スタイナー木
- 準同期式回路のためのクロック配線および遅延挿入手法
- 密度推定に基づく全ネット同時配線手法 : 端点成長法
- スキュー制御クロックネットワークの構成
- 準同期式回路における遅延最適化によるクロック高速化
- クロックスキュー制御によるクロック周期の最小化
- 強パス遅延テスト可能な論理回路の解析と合成
- A-3-3 配線長評価の高速化についての改良手法(A-3.VLSI設計技術,一般セッション)
- A-3-19 多角形パッキングの探索を指向した配置表現方法(A-3.VLSI設計技術,一般セッション)
- 3D-LSIフロアプランの表現方法 : Merged FT Squeeze (物理設計)
- A-1-11 自動マーキングシステムの一手法(A-1.回路とシステム,一般セッション)
- 重ね合わされるプリント基板への素子配置手法(物理設計,システム設計及び一般)
- A-3-3 3次元LSIのフロアプラン探索に適した解空間(A-3.VLSI設計技術,一般セッション)
- A-3-2 最小コストフローを用いた,指定長配線の一手法(A-3.VLSI設計技術,一般セッション)
- 三次元LSIのフロアプラン探索に適した解空間(研究速報)
- アナログ集積回路での近接共通重心配置制約を考慮した配置手法の研究(配置配線,デザインガイア2012-VLSI設計の新しい大地-)
- アナログ集積回路での近接共通重心配置制約を考慮した配置手法の研究(配置配線,デザインガイア2012-VLSI設計の新しい大地-)
- 分枝限定法を用いた,重ね合わされるプリント基板への素子配置手法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- A-3-4 フォトダイオードアレイ(PDA)設計問題の一解法(A-3.VLSI設計技術,一般セッション)
- 矩形分割を重ねて得られる図形による3D-LSIフロアプラン表現(計算機システム)
- 分枝限定法を用いた,重ね合わされるプリント基板への素子配置手法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)
- Simulated Annealing法に基づく自動マーキングシステムの一手法(システムと信号処理及び一般)
- Simulated Annealing法に基づく自動マーキングシステムの一手法(システムと信号処理及び一般)
- Simulated Annealing法に基づく自動マーキングシステムの一手法(システムと信号処理及び一般)
- Simulated Annealing法に基づく自動マーキングシステムの一手法(システムと信号処理及び一般)
- 分枝限定法を用いた,重ね合わされるプリント基板への素子配置手法(ネットワークプロセッサ,通信のための信号処理,無線LAN/PAN,一般)