支配问题的研究进展

作     者：王建新 陈蓓玮 陈建二 WANG Jian-xin CHEN Bei-wei CHEN Jian-er (School of Information Science and Engineering,Central South University,Changsha 410083,China)

作者机构：中南大学信息科学与工程学院长沙410083 

基　　金：国家自然科学基金(60773111) 国家973前期研究专项(2008CB317107) 湖南省杰出青年基金(06JJ10009) 新世纪优秀人才支持计划(NCET-05-0683) 国家教育部创新团队资助计划(IRT0661)资助 

出 版 物：《计算机科学》 (Computer Science)

年 卷 期：2010年第37卷第2期

页      码：7-11页

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

主 题 词：支配问题 点支配集问题 边支配集问题 精确算法 近似算法 参数算法 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203101026...