首页 | 本学科首页   官方微博 | 高级检索  
     

任意图支配集精确算法回顾
引用本文:路纲,周明天,唐勇,吴振强,裘国永,袁柳.任意图支配集精确算法回顾[J].计算机学报,2010,33(6).
作者姓名:路纲  周明天  唐勇  吴振强  裘国永  袁柳
作者单位:1. 陕西师范大学计算机科学学院,西安,710062
2. 电子科技大学计算机科学与工程学院,成都,610054
基金项目:国家自然科学基金(60633020);;国家“八六三”高技术研究发展计划项目基金(2007AA01Z438200);;陕西师范大学科研项目基金(999414)资助~~
摘    要:该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的研究领域.

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

A Survey on Exact Algorithms for Dominating Set Related Problems in Arbitrary Graphs
LU Gang,ZHOU Ming-Tian,TANG Yong,WU Zhen-Qiang,QIU Guo-Yong,YUAN Liu.A Survey on Exact Algorithms for Dominating Set Related Problems in Arbitrary Graphs[J].Chinese Journal of Computers,2010,33(6).
Authors:LU Gang  ZHOU Ming-Tian  TANG Yong  WU Zhen-Qiang  QIU Guo-Yong  YUAN Liu
Abstract: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 ...
Keywords:dominating set  exact algorithm  computational complexity  graph  measure and conquer analysis  
本文献已被 CNKI 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号