带权最大割问题的一种基于划分技术的固定参数可解算法  

Fixed-parameter tractable algorithms based on partition for the weighted maximum cut problem

作　　者：刘运龙[1,2] 王建新[1] 

机构地区：[1]中南大学信息科学与工程学院,长沙410083 [2]湖南师范大学继续教育学院,长沙410013

出　　处：《高技术通讯》2010年第3期264-269,共6页Chinese High Technology Letters

基　　金：973计划(2008CB317107);国家自然科学基金(60433020,60773111);新世纪优秀人才计划(NCET-05-0683);教育部创新团队计划(IRT0661);湖南省杰出青年基金(06JJ10009);湖南省自然科学基金(09JJ3116)资助项目

摘　　要：运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[1n(1/ε)]×2~k(0<ε<1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(1n(1/ε)2~k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2^(2k+12log^2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的。This paper studies the weighted maximum cut problem in terms of the parameterized computational complexity theory. After defining the parmneterized version of the problem, the paper presents a randomized algorithm based on random separation for the parameterized problem. The algorithm randomly bipartitions the vertex set of a given instance for [ln（1/e）]×2^k（0〈ε〈1）times, and returns a k-cut of maximum weight as the output, so that it can obtain the solu- tion with the probability of at least 1 -ε in time O＊（ln（1/ε）2^k）. On the basis of the study above, the paper also pro- poses a deterministic parmneterized algorithm with the time complexity of O＊（2^2k＋12log2（2k） by mainly employing the recent improved （n, k ）-universal set techniques, which shows that the maximum cut problem is fixed-parameter tractable.

关 键 词：带权最大割问题 固定参数可解 随机划分 (n k)-全集 

分 类 号：O221.7[理学—运筹学与控制论]