支配问题的研究进展

• 作者: 王建新 陈建二 陈蓓玮
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 支配问题 点支配集问题 边支配集问题 精确算法 近似算法 参数算法
• 年，卷（期）: 2010,（2）
• 页码范围: 7-11
• 页数: 5页
• 分类号: TP301.6
• 字数: 6247字
• 语种: 中文
• DOI: 10.3969/j.issn.1002-137X.2010.02.002

摘要

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域.支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类.人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法.近年来对参数化支配问题做了大量研究.目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT).利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法.文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王建新	中南大学信息科学与工程学院	371	3185	23.0	39.0
2	陈建二	中南大学信息科学与工程学院	167	1535	20.0	30.0
3	陈蓓玮	中南大学信息科学与工程学院	1	3	1.0	1.0