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

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

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

彭茂

(上海交通大学数学系, 上海 200240)

收稿日期:2009-04-19 修回日期:1900-01-01 出版日期:2010-06-30 发布日期:2010-06-30

A New Kind of Domination in Regular Graphs

PENG Mao

(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

摘要/Abstract

摘要： 在随机正则图中, 研究了图的最小［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.

中图分类号:

O157.5

彭茂. 随机正则图中的一类新控制集[J]. 上海交通大学学报（自然版）.

PENG Mao. A New Kind of Domination in Regular Graphs [J]. Journal of Shanghai Jiaotong University.

[1]	李轩, 谢开贵, 邵常政, 胡博. 基于负荷可行域和可靠性跟踪的电力系统扩容规划及其求解算法[J]. 上海交通大学学报, 2026, 60(2): 200-210.
[2]	范宏, 魏心武, 贾庆山, 罗佳怡. 能源-交通融合下电-气-热多能系统协同优化调度方法[J]. 上海交通大学学报, 2026, 60(2): 211-223.
[3]	. 低渗油井节能生产参数多目标优化方法[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(2): 486-498.
[4]	吴勇华, 梅颖, 卢诚波. 基于增量加权的概念漂移数据流分类算法[J]. 上海交通大学学报, 2026, 60(1): 112-122.
[5]	. SDA-Loc：一种用于点云地图中跨模态定位的语义驱动对齐算法[J]. J Shanghai Jiaotong Univ Sci, 2026, 31(1): 117-129.
[6]	栗大林, 华浩, 李然, 许少伦, 齐文娟. 高功率密度表嵌式磁极偏移永磁电动机转矩性能提升[J]. 上海交通大学学报, 2025, 59(9): 1237-1248.
[7]	刘佳惠, 王聪, 张宏立, 马萍, 李新凯, 董颖超. 代理模型辅助的复杂地形风电场微观选址多目标优化设计[J]. 上海交通大学学报, 2025, 59(9): 1315-1326.
[8]	缪季, 段立平, 刘吉明, 林思伟, 赵金城. 基于改进MCMC算法和代理模型的结构仿真模型更新[J]. 上海交通大学学报, 2025, 59(8): 1114-1122.
[9]	殷旭, 曹冬辉, 田庚, 杨志勋, 范志瑞, 王刚, 陆俣丞, 汪慧. 基于拟物算法的脐带缆截面布局自动填充优化设计方法[J]. 上海交通大学学报, 2025, 59(8): 1103-1113.
[10]	王润谷, 董骁, 龚景海. 单层网壳结构的局部加肋渐进式拓扑优化方法[J]. 上海交通大学学报, 2025, 59(7): 1019-1028.
[11]	庞福滨, 嵇建飞, 吴贤强, 周孟夏, 颜伟, 许东. 特快速暂态过电压对二次侧共模干扰建模[J]. 上海交通大学学报, 2025, 59(6): 812-820.
[12]	曾金灿, 何耿生, 李姚旺, 杜尔顺, 张宁, 朱浩骏. 基于卷积神经网络与轻量级梯度提升树组合模型的电力行业短期以电折碳方法[J]. 上海交通大学学报, 2025, 59(6): 746-757.
[13]	崔思远, 李浩, 范翔宇, 倪磊, 侯佳航. 基于AMDE-DMPC算法的多无人机协同目标搜索方法[J]. 空天防御, 2025, 8(6): 35-44.
[14]	包家汉, 孙德尚, 黄建中, 胡政. 基于自适应阈值的型钢精确角点FAST检测算法[J]. 上海交通大学学报, 2025, 59(5): 691-702.
[15]	. 非视域成像技术研究进展[J]. J Shanghai Jiaotong Univ Sci, 2025, 30(5): 833-854.