確率的なグラフ連結性判定アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
与えられたグラフG=(V, E)が連結か否かを判定することを考える.グラフ全体の構造を保持すれば,O(|V|+|E|)の手間で連結性を判定できることがTarjanによって示されている.本論文では,グラフ全体の構造は保持しないで,グラフの各頂点をある規則に従ってランダムウォークすることによりグラフの連結性を判定するアルゴリズムを扱う.無向グラフを対象として,時間計算量O(|V||E| log |M|),空間計算量O(log |V|)でグラフの連結性を判定するランダムウォークに基づくアルゴリズムが,Aleliunasらにより開発されている.本論文では,簡単な前処理をすることが可能な状況ならば,時間計算量O(|V|^2 log |V|)で無向グラフの連結性が判定できることを示す.また,有向グラフの場合もグラフの直径と正の次数に上界を仮定すると,連結性が多項式オーダで判定できることを示す.
- 一般社団法人情報処理学会の論文
- 2002-09-15
著者
-
品野 勇治
東京農工大学
-
品野 勇治
東京農工大学院共生科学技術研究部
-
品野 勇治
東京農工大学 工学部 情報コミュニケーション工学科
-
池田 諭
東京農工大学工学部情報コミュニケーション工学科
-
中森 眞理雄
東京農工大学
-
中森 眞理雄
東京農工大 大学院共生科学技術研究院
-
中森 眞理雄
東京農工大学 工学府情報工学専攻
-
中森 真理雄
東京農工大学工学部数理情報工学科
-
池田 諭
東京農工大学工学部
-
池田 諭
東京農工大・工
関連論文
- 列生成法を用いたナーススケジューリング問題の解法
- (48) 情報系専門学科のカリキュラムのアイデンティティと評価方法(第4セッション 教育評価方法)
- 17パンケーキグラフの直径計算(パラレルコンピューティングの応用)
- 走査型半導体露光装置における移動順最適化
- 混合整数線形計画法を用いた距離画像の位置合わせ
- 大規模分枝限定木可視化のための適応的木構造グラフ生成(Session 2)
- 単語長を考慮した最長しりとり問題の実験的考察
- 文字数最大しりとり問題の解法
- 最大長しりとり問題の解法
- 準最適解からの加重文脈自由文法の獲得(セッション4)
- 最長しりとり問題とその解法(OR研究の最前線)
- 汎用並列分枝限定法ツールPUBBを用いた最大クリーク問題の厳密解法(整数計画(1))
- 高次元空間における安定集合多面体(整数計画(1))
- 走査型半導体露光装置における移動順最適化(機械力学,計測,自動制御)
- 2-D-4 誤差の離散性を考慮したレンズ調整のロバスト最適化(離散・組合せ最適化(6))
- 分散遺伝的アルゴリズムとローカルサーチを併用した大学の時間割作成システム
- ピュアP2Pネットワーク上における分枝限定法の並列化 : Churn発生時の耐故障性の研究
- 制約2次計画法および2次錐計画法を用いた半導体露光装置用レンズの最適調整(機械力学,計測,自動制御)
- 半導体露光装置におけるレンズ調整 : 群回し調整の最適化(機械力学,計測,自動制御)
- 混合整数計画ソルバーの並列化(パラレルコンピューティングの応用)
- 混合整数線形計画問題を用いた階層的な距離画像の位置合わせ(セッション6)
- 半導体露光装置におけるディストーション調整の最適化(機械力学,計測,自動制御)
- PCクラスタを用いた16パンケーキグラフの直径計算
- 2次割当て問題への適用におけるIntegral Basis Methodの改良の提案
- 分枝限定法における計算過程の可視化(セッション3)
- Particle Swarm Optimizationによる結像光学系の最適化(セッション2)
- 2-F-10 Integral Basis Methodにおける変数選択規則と緩和問題(数理計画(2))
- ステージ格子とディストーションの計測--半導体露光装置におけるソフトウェアデータムの応用
- パンケーキグラフの直径を求める耐障害性のある並列計算システム(セッション3)
- 2次割当問題への適用によるIntegral Basis Methodの改良の提案(セッション3)
- 選択グラフの性質とフローショップスケジューリング問題(アルゴリズム一般)
- 困難な問題の双線形計画問題を用いたモデル化手法
- 論理式充足可能性,整数計画,および双線形計画について
- 作業場所が小さいマージソートと計算量の評価
- 作業領域が小さいマージソート
- パンケーキグラフの直径計算
- トランスポジショングラフにおける素な経路
- n ≥ 14パンケーキグラフの直径計算
- 排他的論理和を含む論理式に対する充足可能性問題
- 特集「情報教育〜理論・評価・発展〜」の編集にあたって
- 資源と作業順序の制約を拡張したスケジューリング問題に対する下界値の計算法
- 情報工学系学科における実験・演習の一設計例
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産における生産ラインのラインバランシング問題に対するヒューリスティックな解法
- 基板生産時における部品装着機の部品吸着順序問題に対する近似解法(セッション4)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 部品装着機における部品供給部への部品割当問題および部品吸着順序問題に対する解法(スケジューリング)
- 基板生産時における部品装着機の部品配置問題および部品吸着順序問題のモデル化と解法
- 変形均衡割当て問題- 2次元ベクトルの場合 -
- 最長しりとり問題の解法
- ネットワークカメラを用いた監視システムの拡張(分散システム構築運用技術,ユーザ指向の分散システム/インターネットの運用・管理)
- 3層チャネル配線における平面配線可能な最大ネット集合の選択手法
- WWWによるアルゴリズム研究支援環境
- アルゴリズムベースのためのグラフアルゴリズムの部品化
- 電子メールのオブジェクト指向データベースによる管理方法の提案
- 対象の代数構造を重視したアルゴリズム記述法
- 方形チップ格子上のウェーハ配置最適化(VLSI設計技術とCAD)
- 方形チップ格子上のウェーハ配置最適化
- 取得チップ数を最大化するウエハ配置(ケース・スタディ)
- [チュートリアル講演]局所情報を用いる有限グラフ上の乱歩のヒッティング時間とカバー時間
- 局所情報を利用するグラフ上のランダムウオークのカバータイムについて
- 分枝限定法における分枝戦略選択のための計算過程の可視化
- 7)放送衛星波の小口径アンテナによる受信CN比の年間特性について(無線・光伝送研究会)
- 放送衛星波の小口径アンテナによる受信CN比の年間特性について
- 27-1 BSにおける雨、露によるCN比変動について
- 並列分枝限定法を用いた容量制約付き枝巡回路問題の厳密解法(組合せ最適化(3))
- 2次割当問題に対するIntegral Basis Method(離散最適化)
- CPLEX MIP OptimizerのPUBB2フレームワークによる並列化について(整数計画(2))
- 混合整数計画問題の解法における前処理の効果検証(整数計画(2))
- 2108 半導体露光装置におけるディストーション補正の最適化(OS21 設計と最適化II)
- 半導体露光装置のステージ格子計測法
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- メッセージ遅延の影響評価のための並列分散プログラムシミュレータの研究
- 確率的なグラフ連結性判定アルゴリズム
- 電子部品装着機の装着順序決定アルゴリズムの研究
- 不完全な部品の組合せ問題について(II) : 誤差がベクトルの場合
- メモリ領域が小さい確率的なグラフ連結性判定アルゴリズムについて
- 分枝限定法並列化ツールPUBB (アルゴリズム工学)
- 並列分枝限定法における解の探索規則
- 完全分散型分枝限定法並列化ツールの設計(組合せ最適化(2))
- 静止衛星回線に見られる太陽雑音妨害
- 航空機散乱波によるテレビ受信電界のモデル計算
- WWW上におけるアルゴリズムアニメーションシステムの構築
- WWW上におけるアルゴリズムアニメーションシステムの構築
- PCクラスタを用いたHEXにおける最善応手手順の生成(組合せ最適化(1))
- PUBBによるPCクラスタ環境における並列分枝限定法 (新しいパラダイムとしてのアルゴリズム工学)
- PCクラスタ環境における並列分枝限定法(数理計画(2))
- 汎用並列分枝限定法ツールPUBBによる組合せ最適化問題の厳密解法 (特集「計算と最適化」)
- 完全分散型並列分岐限定法システムのアーキテクチャと負荷分散(最適化の数理における離散と連続構造)
- 分枝限定法における並列処理 : 分枝限定法並列化ツールPUBB
- 分枝限定法における並列処理の研究(組合せ・グラフ・ネットワーク)
- Hausdorff測度とpacking測度が同等となるフラクタル集合のあるクラスについて
- 3D-12 障害物のある場合の警備員経路問題に関する研究
- 障害物のある警備員経路問題に関する研究
- 12)衛星放送受信に見られる太陽雑音妨害によるC/N特性(無線・光伝送研究会)
- 衛星放送受信に見られる太陽雑音妨害によるC/N特性
- 11)放送衛星のCN比と気象現象について(無線・光伝送研究会)
- 放送衛星のCN比と気象現象について
- 衛星放送受信に見られる太陽雑音妨害によるC/N特性