The infection time of graphs

Tassos Dimitriou, Sotiris Nikoletseas and Paul Spirakis
Discrete Applied Mathematics
Volume 154, Issue 18 , 1 December 2006, Pages 2577-2589
http://dx.doi.org/10.1016/j.dam.2006.04.026

グラフ(の頂点集合)上に赤い粒子1個と白い粒子k-1個が置かれていて，これらが離散的なランダムウォークをする．
白い粒子が赤い粒子と(頂点上で)出会うと白い粒子は赤い粒子に変わる．
全ての白い粒子が赤い粒子になるまでにどれだけ時間がかかるか，という問題を考えた研究．
いわゆる，モバイル計算や自律分散計算を念頭においていて，理論的な結果と実験的な結果の両方が掲載されている．
面白い問題だと思う．