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

摘要：

运用参数计算复杂性理论和技术对带权最大割问题进行了研究.首先对该问题及其相关概念进行了参数化定义,然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法.该随机算法依次将实例图的顶点进行「ln(1/ε)」×2~k(0<ε<1)次随机划分,并选择其中权值最大的k-划分作为输出解,因而能在时间O~*(ln(1/ε)2~k)内以至少1-ε的概率找到目标解.接着在此基础上着重运用最新改进的(n,k)-全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O~*(2~(2k+12log~2(2k))的确定性算法,表明了带权最大割问题是固定参数可解的.

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

所属期刊栏目：20

分类号：O22;TP3

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

在线出版日期：2010-05-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：264-269