上海交通大学学报

上海交通大学学报（自然版）

• 数学 • 上一篇    下一篇

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

彭茂   

  1. (上海交通大学 数学系, 上海 200240)
  • 收稿日期:2009-04-19 修回日期:1900-01-01 出版日期:2010-06-30 发布日期:2010-06-30

A New Kind of Domination in Regular Graphs

PENG Mao   

  1. (Department of Mathematics, Shanghai Jiaotong University, Shanghai 200240, China)
  • Received:2009-04-19 Revised:1900-01-01 Online:2010-06-30 Published:2010-06-30

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

关键词: 随机正则图, 算法, 连通控制集

Abstract: 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.

中图分类号: