有限グラフ上のランダムウォークの脱乱択化
スポンサーリンク
概要
- 論文の詳細を見る
Propp 機械,あるいは rotor-router モデルは,ランダムウォークを模倣する決定的過程である.ランダムウォークにおいては,グラフ上をトークンがランダムに巡回するのに対し,Propp 機械においては,各頂点上の router があらかじめ定められた隣接点の順番に従って,トークンを隣接点に発射する.本稿では,有限グラフ上の Propp 機械に着目し,ランダムウォークモデルにおけるトークンの期待配置と Propp 機械におけるトークンの配置の誤差の上下界を見積もる.より正確には,任意のグラフに対し,単一頂点誤差が O(mn) であることを示す.ただし,m は枝数,n は頂点数を表す.下界としは,単一頂点誤差が Ω(m) となるようなグラフと配置を与える.
- 2011-05-09
著者
関連論文
- 点集合間の辺連結度を増大させる問題
- グラフクラスと部分グラフ同型性
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- 安心・安全社会構築のためのシステム人間科学の創成(テーマ関連/オーガナイズドセッション1)
- 1-D-13 Sampling from Logarithmic Separable Concave Distribution on Simplex
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4, 日本計算機統計学会第18回大会報告)
- 離散化Dirichlet分布に従うパーフェクトサンプリング(セッション4)
- 離散化Dirichlet分布に従うPerfect Sampler(マルコフモデル)
- MCMC法による2×n分割表個数数え上げ(セッション5)(日本計算機統計学会第16回大会報告)
- 順列制約をみたす模調要求をもつ正モジュラシステムについて
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- ホーン理論の内包・外包に対する演繹推論
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ストリーミング中の頻出アイテム発見アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- 有限グラフ上のランダムウォークの脱乱択化
- ストリーム中の頻出アイテム発見に対するO(loglogN) 領域乱択アルゴリズム
- コーダルグラフのサンドイッチ列挙
- m×n分割表の近似数え上げスキームの提案(マルコフ連鎖)
- 2×n分割表のPerfect Sampling(マルコフ連鎖)
- m×n分割表の近似数え上げスキームの提案
- MCMC法による2×n分割表個数数え上げ(一般講演)
- 1-D-4 木構造動的ネットワークにおけるα-最速到達フロー(離散アルゴリズム(1))
- 2-I-4 整数線形システムの実行可能性問題に対する計算複雑さの指標(離散最適化(3))
- 2-I-3 ネットワークデザインゲームにおけるポテンシャル最小化(離散最適化(3))
- 1-D-3 グラフ上のランダムウォークとその高速化(特別セッション 若手によるOR横断研究)
- 単調な論理関数の双対化について
- DS-1-16 完全非同期ロボットによるパターン形成(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 ストリーム中の頻出アイテム発見に対するO(loglogN)領域乱択アルゴリズム(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 無理数遷移確率ランダムウォークの脱乱択化
- 1-C-8 キャンセルコスト付きオンラインナップサック問題(離散最適化(1))
- 1-C-10 疎な線形相補性問題に対する組合せ的アルゴリズム(離散最適化(1))
- 無理数の遷移確率を許すランダムウォークの脱乱択化 (理論計算機科学の新展開)
- 森および連結全域部分グラフの乱択近似数え上げ (理論計算機科学の新展開)
- 2-B-1 パリティ最長路問題(離散最適化(4))
- 1-F-9 無理数の遷移確率をもつランダムウォークの脱乱択化(確率モデル(3))
- 1-B-7 ラーマングラフの局所遷移可能性(離散最適化(2))
- ストリームに対するO(loglogn)領域を用いたReservoir sampling(一般)
- DS-1-14 関数ルーターモデルの提案(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-15 森および連結全域部分グラフの乱択近似数え上げ(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- DS-1-17 動的グラフ上のランダムウォークの到達時間と全訪問時間(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 安定結婚問題における最大最適選好マッチングの頂点集合の一意性(一般)
- 関数ルーターモデルによるハイパーキューブ上ランダムウォークの脱乱択化(一般)
- 2-A-11 ロバスト独立システム(離散最適化(3))