论文部分内容阅读
运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义，然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[ln（1／e）]×2^k（0〈ε〈1）次随机划分，并选择其中权值最大的七一划分作为输出解，因而能在时间O＊（ln（1／ε）2^k）内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的（n，k）．全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O＊（2^2k＋12log2（2k）的确定