图的连通支配集构造算法研究

项目名称： 图的连通支配集构造算法研究

项目编号： No.61173002

项目类型： 面上项目

立项/批准年度： 2012

项目学科： 自动化技术、计算机技术

项目作者： 赵承业

作者单位： 中国计量学院

项目金额： 55万元

中文摘要： 连通支配集是图的支配理论中一个比较新的领域，关于图的连通支配集的构造算法研究在无线网络应用技术中有着广泛的应用。确定一个图的最小连通支配集是NPC问题，即使是对结构相对简单、有相应构造规则的图，其构造问题也十分复杂。本项目研究广义Petersen图等图类的连通支配集的构造问题。通过理论分析和计算所研究的图类的最小连通支配集上下界；然后利用计算机构造和搜索，将所研究的图类分成几个子类来分别考虑。重点研究满足最小支配集下界的子类，利用这类图的全局性质和局部性质，将其连通支配集划分为规则结构模式与非规则结构模式，建立相应的模式库。在此基础上，研究不同参数下规则结构模式的构成规律，探讨不同参数下的非规则结构模式是否存在统一的形式。通过研究规则结构模式和非规则结构模式的组合性质给出所研究图类的连通支配集构造算法。本项目研究提供了构造图的连通支配集的一个新思路，为无线网络技术提供理论和应用基础。

中文关键词： 连通支配集；正则图；[1;2]-支配集；复杂网络；社团结构

英文摘要：

英文关键词： connected dominating set；regular graph；[1;2]-dominating set；complex network；community structure