随机正则图中的一类新控制集

A New Kind of Domination in Regular Graphs

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

An [r,R]-dominating set is a distance r-dominating set which can be connected by adding paths with length within R.In this paper,it was restricted in random regular graphs and several algorithms were designed to approximate the minimum [r,R]-dominating set.After analyzing its average performance by using differential equations,an upper bound was achieved as well.