| 支配问题的研究进展 |
| |
| 引用本文： | 王建新,陈蓓玮,陈建二.支配问题的研究进展[J].计算机科学,2010,37(2):7-11. |
| |
| 作者姓名： | 王建新 陈蓓玮 陈建二 |
| |
| 作者单位： | 中南大学信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金(60773111);;国家973前期研究专项(2008CB317107);;湖南省杰出青年基金(06JJ10009);;新世纪优秀人才支持计划(NCET-05-0683);;国家教育部创新团队资助计划(IRT0661)资助 |
| |
| 摘 要： | 复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。
|
| 关 键 词： | 支配问题 点支配集问题 边支配集问题 精确算法 近似算法 参数算法 |
| 收稿时间： | 3/9/2009 12:00:00 AM |
| 修稿时间： | 2009/5/25 0:00:00 |
Algorithms for Dominating Problems:A Survey |
| |
| WANG Jian-xin,CHEN Bei-wei,CHEN Jian-er.Algorithms for Dominating Problems:A Survey[J].Computer Science,2010,37(2):7-11. |
| |
| Authors: | WANG Jian-xin CHEN Bei-wei CHEN Jian-er |
| |
| Affiliation: | School of Information Science and Engineering/a>;Central South University/a>;Changsha 410083/a>;China |
| |
| Abstract: | In complexity theory,dominating problem is an important problem,which has important applications in many fields such as resource allocations,electric networks and wireless ad hoc networks.The two most known dominating problems are Vertex Dominating Set(VDS) and Edge Dominating Set(EDS) problem.People designed and analyzed exact algorithms for the two problems by dynamic programming and measure-and-conquer techniques and proposed many approximation algorithms for EDS problem by reducing the problem to Edge C... |
| |
| Keywords: | Dominating problem Vertex dominating set problem Edge dominating set problem Exact algorithm Approximation algorithm Parameterized algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
点击此处可从《计算机科学》下载全文 |
