完美图的电力控制集问题及其推广问题的算法研究

项目名称： 完美图的电力控制集问题及其推广问题的算法研究

项目编号： No.61202021

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 计算机科学学科

项目作者： 陈磊

作者单位： 上海海事大学

项目金额： 23万元

中文摘要： 图的控制集理论是目前图论研究中发展最快的领域之一，并且随着各种形式控制集问题的引入，其研究更为广泛而深入。电力控制集问题以其独特的控制条件和较强的应用背景，目前已经引起很多学者的关注。从现有的研究状况来看，该问题在完美图上的研究成果较经典的控制集问题而言有较大的"缺口"。故本项目拟对电力控制集问题在完美图上做一些研究工作，主要的研究内容为：一、用多项式时间归约确定电力控制集问题在完美图的哪些子图类上是NP-完全的；二、用标号方法、动态规划、线性规划等方法设计电力控制集问题在完美图的子图类上的多项式时间算法；三、引入电力控制集问题的推广形式f-电力控制集问题，并给出其在一些图类(如树、区间图等)上的多项式时间算法。通过本项目的研究，能得到一些新的算法和较深刻的新结果，进一步完善图的控制集理论。

中文关键词： NP-完全；多项式时间算法；控制集；k-电力控制集；

英文摘要： Domination theory in graphs is now one of the fastest-growing areas within graph theory. The study of this problem is extensive and in-depth with the introduction of different kinds of domination problems. At present, more and more researchers begin to pay attention to power domination problem due to its special conditions and applications. View from the present research progress, there are many unsolved issues for this problem in perfect graphs compared to the results of classic domination problem. Thus this project is to investigate power domination problem in perfect graphs. The major research topics include: (1) Using polynomial-time reduction to determine the sub-classes of perfect graphs for which power domination problem is NP-complete. (2) Utilizing some methods, such as labeling method, dynamic programming, linear programming, etc, to design some polynomial-time algorithms in some sub-classes of perfect graphs; (3) Introduction of a new generalization of power domination problem, named f-power domination problem, and some polynomial-time algorithms will be given for this new problem in some special graphs, such as trees, interval graphs, etc. The purpose of this project is to design some new algorithms and obtain some new in-depth results, which can make domination theory in graphs more perfect.

英文关键词： NP-complete；Polynomialtime-time algorithm；Domination；k-power domination；