随机正则图中的一类新控制集 (2010年)

在随机正则图中，研究了图的最小[r, R]控制集的定界问题。基于随机策略，提出了求解图的最小[r, R]控制集的近似算法，跟踪算法执行过程中相关参数的期望值变化情况，列出相应的带初值条件的常微分方程，通过对方程解的估计衡量该算法的平均性能。在此算法的分析基础上，给出了最小[r, R]控制集的一个上界。