最小カット問題に対するKargerのランダムアルゴリズムの新しい確率的評価について
スポンサーリンク
概要
- 論文の詳細を見る
Gをn個の節点をもつ無向グラフとする.Kargerはグラフの最小カット問題に対してランダムアルゴリズムを与えた.そのアルゴリズムは確率Ω(n^<-2>)でグラフのある特定の最小カットを見つける.本論文はKargerのアルゴリズムに対して新しい確率的評価を与える.ランダムグラフの特定の最小カットを見つける確率の期待値はΩ(p/n)であることを示す.ただし,pは枝を選ぶ確率である.さらに,密な一般グラフに対しても新しい結果を示す.
- 1994-07-22
著者
-
岩野 和生
日本IBM株式会社大和ソフトウェア開発研究所
-
戴 陽
神戸商科大学管理科学科
-
加藤 直樹
神戸商科大学管理科学科
-
戴 陽
Bioeng. Dept., Univ.
-
戴 陽
東京工業大学情報理工学研究科数理・計算科学専攻
-
加藤 直樹
神戸商科大学
-
岩野 和生
日本アイ・ビー・エム(株)
-
岩野 和生
日本ibm
関連論文
- 実大4層鉄骨造建物のブラインド解析コンテストの総括と解析精度の検討
- 東京5区内のオフィスビルへのテナント入居と空室期間に関する分析
- 一様点要求を満たす根つき森分割と剛性理論への応用
- 1-D-8 動的ネットワークフローを用いた避難所の収容人数の評価(離散・組合せ最適化(3))
- 大学における情報化戦略と理工系情報学科の貢献
- 柔な構造による免震デバイスモデルの形状最適化
- 最小カット問題に対するKargerのランダムアルゴリズムの新しい確率的評価について
- クラウド・コンピューティングの動向とIBMの取組み
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 巡回カメラマン問題とその自動光学的検査への応用
- TSP解法の実験的解析とそれに基づく2-Optと相性のよいツアー構築法の提案
- サポートベクトルマシンにおける例外の影響力の定め方について
- Provably Fast Training Algorithms for Support Vector Machines
- TD-1-4 サンプリング技法でエラーを抽出する方法について
- 20146 E-Simulatorによる鋼構造超高層骨組の仮想震動実験と骨組解析の比較(極限解析・崩壊挙動解析,構造I)
- 不完全情報下での複数人の探索者によるグラフ探索問題
- 5336 経路障害発生時の集団経路探索行動における情報共有の有効性に関する理論的研究(経路探索,建築計画I)
- 8083 東京23区内のオフィスビルへのテナントの入居期間の分析(オフィスビル・REIT,建築社会システム)
- 7386 CAEPを用いた京都市郊外におけるひったくりの空間分析(居住空間の防犯,都市計画)
- 20416 三角形パッチベジエ曲面による区分的可展シェルの形態創生(骨組の形態創生,構造I)
- 20409 異方性を有するフィルタ関数を用いた軸対称シェルのトポロジー最適化(連続体の形態創生,構造I)
- 20390 二面体群対称とテンセグリティ構造の安定性(テンセグリティ・ハイブリッド構造(1),構造I)
- 20200 数値震動台プロトタイプによる鋼構造超高層骨組および4層骨組の仮想震動実験(大規模解析,構造I)
- 20455 骨組膜構造物の定着金物の応力制約下での形状最適化(膜構造(1),構造I)
- 20454 骨組膜構造物の定着部拘束力最大化のための形状最適化(膜構造(1),構造I)
- 8043 超高層集合住宅のリスク情報共有システムの開発(生産情報・評価,建築社会システム)
- 20411 ラチスシェルの部材長一様化制約下でのひずみエネルギー最小化(形態創生・最適化(1),構造I)
- 分数制約をもつマルコフ決定過程
- イメージ切り出しに関するアルゴリズム
- 7505 大阪府の家電メーカー取引関連企業の移転に関する分析(人口分布・街区密度,都市計画)
- LMT-skeletonに関する一考察
- 8060 空間属性を考慮したオフィスビルの貸室の賃料推定に関する研究(マネジメント,建築社会システム)
- 製造業における巡回セールスマン問題の応用
- サーキットボード穴開け問題
- 最大流アルゴリズムの最近の発展とその背景 : II
- 最大流アルゴリズムの最近の発展とその背景 : I
- 「情報アクセシビリティー : 高齢者, 障害者からはじまる新しい情報パラダイム」
- ランダマイズドクラスタリングアルゴリズムに関する実験結果について
- イメージ切り出しの効率的アルゴリズム
- A New Probabilistic Evaluation of Karger's Randomized Algorithm for Minimum Cut Problems
- Randomized Algorithms for Variance-Based $k$-Clustering
- 点集合を分散の総和が最小となるようにk個のクラスターに分割するアルゴリズム
- A New Randomized Approach to the Minimum Cut Problem and Its Variants by Minimum Range Cut Algorithms
- 特集にあたって(最適化とその応用)
- パラメトリック最適化問題とその応用
- ある種の団体戦競技における出場順序と勝利確率の関係に関する数学的考察
- 伊理正夫・藤重悟・大山達雄 著, グラフ・ネットワーク・マトロイド
- 樹脂建材生産における板取り(板取り)
- 離散型資源の公平な配分方法
- 分散型システムにおける相互排除のためのトークンを用いたスキームについて(計算機構に関する数学的基礎理論とその応用)
- 二目的フローショップ・スケジューリング問題に対する遺伝的アルゴリズム
- 大学における情報化戦略と理工系情報学科の貢献(パネル討論)
- 「最適化とその応用」研究部会終了報告(ペーパーフェア)
- 「最適化とその応用」研究部会中間報告(ペーパーフェア)
- 分枝限定法による分散最小化問題の厳密解法(数理計画)
- ディジタル画像における直線成分抽出のためのアルゴリズム
- 連鎖的アボートのない多版先読みスケジューラ
- 良い『メモリ図』の生成
- 新しい社会サービスの実現に向けてその課題と解決策を考える
- 1808 ソリッド要素を用いた鋼構造4層骨組の高精度有限要素解析(OS18.社会・環境・防災シミュレーション(2),オーガナイズドセッション)
- 2105 柔な構造による免震デバイスモデルのトポロジー最適化(OS21.計算力学と最適化(2),オーガナイズドセッション)
- A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images
- 画像処理における組合せ最適化問題(情報化社会における最適化)
- 線形分数関数最適化とその応用
- 角度制約付き最適な三角形分割の計算について
- 最大格差最小k-カットアルゴリズムによる最小k-カット問題の近似解法 (組合せ最適化)
- 画像解析によるポリ塩化ビニル樹脂系防水シートの伸び保持率の推定
- 物理的世界とデジタルの世界の融合がもたらすもの Smarter Planet の目指す世界
- マネジメント最前線1 新技術が社会と企業にもたらすもの (特集 グリッド・コンピューティング)
- シミュレーション技術への期待
- 巡回セールスマン問題をめぐる最近の話題
- 理論と実際の邂逅の場としての情報処理学会
- 548 柔構造のトポロジー最適化による上下方向免震装置の設計(動力学問題の最適設計とその周辺技術と応用,OS-14 動力学問題の最適設計・制御とその周辺技術と応用,総合テーマ「伝統を,未来へ!」)
- 団体戦の最適出場順序に関する数理的考察(スポーツの数理)
- 2115 偏心ブレース架構のエネルギー消費性能を考慮したリンク部材形状最適化(構造)
- 1-I-10 非同形な静定グラフの列挙アルゴリズム(離散最適化(2))
- 2-C-7 大阪主要オフィスエリアにおける企業立地・移転要因に関する分析(都市・地域・国土(1))
- 空間構造物の2方向応答制御のためのコンプライアントメカニズムで構成されたマスダンパーのパラメータ最適化
- 東京都23区内のオフィスビル点検・修理業務の定量分析と管理拠点の最適配置に関する研究
- 4.組合せ剛性理論に基づく構造物列挙(広がる列挙の技術-列挙による問題解決アプローチ-)
- DS-1-12 組合せ剛性理論に基づく冗長性を有する剛堅な2次元フレームワークの生成手法(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ディジタル画像における直線成分抽出のためのアルゴリズム(計算幾何学と離散幾何学)
- 計算幾何学的手法の画像処理への応用
- 計算幾何学的手法の画像処理への応用
- 1-D-6 組合せ剛性理論に基づく冗長性を有する剛堅な2次元フレームワークの生成手法(離散最適化(1))
- 20336 2方向制振性能を有するマスダンパーの最適設計(立体骨組の振動(2),構造I)
- 20162 鋼構造骨組の材料と断面パラメータの不確定性を考慮した最適設計(骨組の最適化,構造I)
- 20155 E-Simulatorによる合成梁の高精度コンポーネント解析(部材解析,構造I)
- 20117 E-Simulatorによる4層鋼構造骨組の仮想震動実験と骨組解析の比較(数値解析法・骨組の振動,構造I)
- 8058 東京都23区内のオフィスビル点検・修理業務の定量分析と業務拠点の最適配置に関する研究(プログラミング・維持管理,建築社会システム)
- 組合せ剛性理論に基づく構造物列挙
- 22304 偏心ブレース架構のエネルギー消費性能最適化(梁材(1),構造III)