欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
运用参数计算复杂性理论和技术对带权最大割问题进行了研究。首先对该问题及其相关概念进行了参数化定义，然后对参数化带权最大割问题提出了一种基于随机划分技术的随机算法。该随机算法依次将实例图的顶点进行[ln（1／e）]×2^k（0〈ε〈1）次随机划分，并选择其中权值最大的七一划分作为输出解，因而能在时间O＊（ln（1／ε）2^k）内以至少1-ε的概率找到目标解。接着在此基础上着重运用最新改进的（n，k）．全集划分技术对参数化带权最大割问题提出了一个时间复杂度为O＊（2^2k＋12log2（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.
同期刊论文项目
同项目期刊论文
Significant linkage and association between a functional (GT)n polymorphism in promoter of the N-met
A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments an
Modifying the DPClus algorithm for identifying protein complexes based on new topological structures
Approximation algorithm based on chain implication for constrained minimum vertex covers in bipartit
A modified particle swarm optimization-based dynamic recurrent neural network for identifying and co
期刊信息
位置：