任意图支配集精确算法回顾

摘要：

该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集,最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的研究领域.

关键词：支配集、精确算法、计算复杂性、图、测度分析技术

所属期刊栏目：33

分类号：TP393(计算技术、计算机技术)

资助基金：国家自然科学基金60633020;国家"八六三"高技术研究发展计划项目基金2007AA01Z438200;陕西师范大学科研项目基金999414

在线出版日期：2010-08-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：1073-1087