计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2010年
7期
1140-1152
,共13页
反馈顶点集%无向图%带权%参数%固定参数枚举
反饋頂點集%無嚮圖%帶權%參數%固定參數枚舉
반궤정점집%무향도%대권%삼수%고정삼수매거
反馈顶点集(FVS)问题是一个经典的NP-完全问题,在很多领域有重要的应用.人们对该问题进行了大量的研究,但目前还没有有效的算法枚举带权无向图的反馈顶点集.文中通过对带权无向图中反馈顶点集问题的结构的深入分析,给出了一个有效的基于分支搜索技术的固定参数枚举算法.算法将反馈顶点集问题转化为反馈边集问题,通过枚举z个权值最大的森林来枚举z个权值最小的含k条边的反馈边集,从而得到z个权值最小的含k个顶点的反馈顶点集,算法时间复杂度为O(5kn2(logn+k)+3kz(n2logn+z)).
反饋頂點集(FVS)問題是一箇經典的NP-完全問題,在很多領域有重要的應用.人們對該問題進行瞭大量的研究,但目前還沒有有效的算法枚舉帶權無嚮圖的反饋頂點集.文中通過對帶權無嚮圖中反饋頂點集問題的結構的深入分析,給齣瞭一箇有效的基于分支搜索技術的固定參數枚舉算法.算法將反饋頂點集問題轉化為反饋邊集問題,通過枚舉z箇權值最大的森林來枚舉z箇權值最小的含k條邊的反饋邊集,從而得到z箇權值最小的含k箇頂點的反饋頂點集,算法時間複雜度為O(5kn2(logn+k)+3kz(n2logn+z)).
반궤정점집(FVS)문제시일개경전적NP-완전문제,재흔다영역유중요적응용.인문대해문제진행료대량적연구,단목전환몰유유효적산법매거대권무향도적반궤정점집.문중통과대대권무향도중반궤정점집문제적결구적심입분석,급출료일개유효적기우분지수색기술적고정삼수매거산법.산법장반궤정점집문제전화위반궤변집문제,통과매거z개권치최대적삼림래매거z개권치최소적함k조변적반궤변집,종이득도z개권치최소적함k개정점적반궤정점집,산법시간복잡도위O(5kn2(logn+k)+3kz(n2logn+z)).
