Deterministic Random Walk

确定性随机游走

• 批准号: 23650007
• 负责人: KIJIMA Shuji
• 金额: $ 2.33万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Exploratory Research
• 财政年份: 2012
• 资助国家: 日本
• 起止时间: 2012 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23650007/
• 关键词: アルゴリズム理論; マルコフ連鎖; 脱乱択化

The rotor-router model, which is sometimes called deterministic random walk, is a deterministic process analogous to a random walk on a graph. In this project, we have investigated the rotor-router model, aiming at a new scheme for derandomization of randomized algorithms. While most previous works concerning the rotor-router model dealt with simple random walks on regular graphs, we have proposed some extended models to deal with general transition probability, and have developed techniques for analysis of discrepancies between the models and random walks

转子路由器模型，有时也称为确定性随机游走，是一个类似于图上随机游走的确定性过程。在这个项目中，我们研究了转子路由器模型，旨在为随机算法的去随机化提供一个新的方案。虽然以前大多数关于转子路由器模型的工作都是处理规则图上的简单随机游动，但我们提出了一些扩展模型来处理一般转移概率，并开发了分析模型和随机游动之间差异的技术

项目成果

Probability and Computation

概率与计算

• 期刊: ICNC 2011: 345-3462011 Second International Conference on Networking and Computin
• 作者: kada Y;Reinach PS;Kitano A;Shirai K;Kao WW;Saika S.;Shuji Kijima
• 通讯作者: Shuji Kijima

Deterministic random walks on finite graphs

有限图上的确定性随机游走

• DOI: 10.1002/rsa.20533
• 发表时间: 2015
• 期刊: Random Struct. Algorithms
• 作者: Shuji Kijima;Kentaro Koga;Kazuhisa Makino
• 通讯作者: Kazuhisa Makino

Deterministic random walk on finite graphs

有限图上的确定性随机游走

• 发表时间: 2013
• 作者: 白髪丈晴,山内由紀子;来嶋秀治;山下雅史;Shuji Kijima
• 通讯作者: Shuji Kijima

関数ルーターモデルの提案

功能路由器模型的提案

• 发表时间: 2013
• 作者: 白髪丈晴，山内由紀子;来嶋秀治;山下雅史
• 通讯作者: 山下雅史

有限グラフ上のランダムウォークの脱乱択化

有限图上随机游走的去乱

• 发表时间: 2011
• 作者: 来嶋秀治;古賀健太郎;牧野和久
• 通讯作者: 牧野和久