《计算机学报》文章摘要   全文下载
文章题目	任意图支配集精确算法回顾
作者	路纲1) 周明天2) 唐勇2) 吴振强1) 裘国永1) 袁柳1)
作者单位	1)(陕西师范大学计算机科学学院 西安 710062) 2)(电子科技大学计算机科学与工程学院 成都 610054)
发表年份	2010
发表月份	6期(1073—1087)
文章摘要	摘要 该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明，以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后，经过很长一段时期的沉寂，关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外，作者还盼望国内研究团体能更加重视这个快速发展的研究领域. 关键词 支配集；精确算法；计算复杂性；图；测度分析技术 中图法分类号 TP393 DOI号: 10.3724/SP.J.1016.2010.01073