| 刘运龙,王建新.带权最大割问题的一种基于划分技术的固定参数可解算法[J].高技术通讯(中文),2010,20(3):264~269 |
| 带权最大割问题的一种基于划分技术的固定参数可解算法 |
| Fixed parameter tractable algorithms based on partition for the weighted maximum cut problem |
| |
| DOI： |
| 中文关键词: 带权最大割问题， 固定参数可解， 随机划分， (n,k) 全集 |
| 英文关键词: weighted maximum cut, fixed parameter tractable, random separation, (n,k) universal set |
| 基金项目:973计划(2008CB317107)，国家自然科学基金(60433020，60773111)，新世纪优秀人才计划(NCET 05 0683)，教育部创新团队计划(IRT0661)，湖南省杰出青年基金(06JJ10009)和湖南省自然科学基金(09JJ3116)资助项目 |
| 作者 | 单位 | | 刘运龙 | 中南大学信息科学与工程学院；湖南师范大学继续教育学院 | | 王建新 | 中南大学信息科学与工程学院 |
|
| 摘要点击次数: 2688 |
| 全文下载次数: 2303 |
| 中文摘要: |
| 运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义，然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行「ln(1/ε)?×2k(0<ε<1)次随机划分，并选择其中权值最大的k 划分作为输出解，因而能在时间O(ln(1/ε)2k)内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的(n,k) 全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O(22k+12log2(2k))的确定性算法，表明了 |
| 英文摘要: |
| This paper studies the weighted maximum cut problem in terms of the parameterized computational complexity theory. After defining the parameterized 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/ε)?×2k (0<ε<1) times, and returns a k cut of maximum weight as the output, so that it can obtain the solution with the probability of at least 1-ε in time O(ln(1/ε)2k). On the basis of the study above, the paper also proposes a deterministic parameterized algorithm with the time complexity of O(22k+12log2(2k)) by mainly employing the recent improved (n,k) universal set techniques, which shows that the maximum cut problem is fixed parameter tractable. |
|
查看全文
查看/发表评论 下载PDF阅读器 |
| 关闭 |
