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

A Survey on Exact Algorithms for Dominating Set Related Problems in Arbitrary Graphs

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

This paper provides a review on recent advances in the analysis and design of exact algorithms for domination in arbitrary graphs.The dominating set problem is one of the classical NP-complete problems and fits into broader class of domination problems.The authors provide the detailed algorithms,which have been very recently obtained,and illustrations for the domination problems in arbitrary graphs including minimum dominating set,maximum independent set,minimum independent dominating set,minimum connected dominating set and minimum weighted dominating set for the purpose of making the paper be self-contained and easy reading.Several techniques such as Branch Reduce,Complexity analysis,Measure Conquer,Memorization and so on are also discussed.After a long period of silence since Claude Berge formulated for the first time of modern conception of domination,the interest in design of exact exponential time algorithms has been growing significantly within the last five years.In addition to present a view of the latest results,the authors also hope more domestic research communities would pay attention to this rapidly developed field of research.