顶点加权最大团问题的加权分治算法

数学理论与应用 ›› 2017, Vol. 37 ›› Issue (2): 97-104.

顶点加权最大团问题的加权分治算法

黄飞¹ ，宁爱兵¹，刘志民¹ ，何咏梅¹ ，王永斐² ，张惠珍¹

1.上海理工大学管理学院,上海,200093; 2.58安居客,上海,200127

出版日期:2017-06-30 发布日期:2020-09-23
基金资助:
国家自然科学基金(71401106);

上海市一流学科建设项目资助(S1201YLXK);

高等学校博士学科点专项科研基金联合资助课题(20123120120005)

Measure and Conquer Approach for the Maximum Vertex Weighted Clique Problem

Huang Fei ¹，Ning Aibing¹， Liu Zhimin¹， He Yongmei¹， Wang Yongfei ²， Zhang Huizhen¹

1.School of Business,University of Shanghai for Science and Technology,Shanghai 200093,China; 2.58Anjuke,Shanghai 200127,China

Online:2017-06-30 Published:2020-09-23

摘要/Abstract

摘要： 分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656ⁿp(n)),其中n 代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656ⁿp(n))降为O(1.3765ⁿp(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度.

关键词:

"> 分支降阶算法, 顶点加权最大团问题, 时间复杂度, 加权分治, 图论

Abstract:

Branching and order-reducing are widely used for solving NP-Hard Problems.The main idea of the approach is to solve the problem by decomposing it into two or more sub-problems,and the sub-problems can be recursively solved.But we cannot get a better result by using the normal complexity analyticalmethod since it is not so accurate.The measure and conquer approach is a new technique for algorithm design and complexity analysis.This paper designs an algorithm to solve the weighted maximum clique problem and uses traditional analysis technology to analyze the worst-case running time of the algorithm and gets O(1.4656ⁿp(n))running time,where p(n)is the polynomial function of node number nin the problem.We employ the measure and conquer approach to improve the time complexity of the algorithm from O(1.4656ⁿp(n)) to O (1.3765ⁿp(n))without modifying the algorithm. Our results show that the measure and conquer approach can give more precise time complexity.

Key words:

Branching and order-reducing algorithm, Weighted maximum clique, Time complexity, Measure and conquer, Graph theory

黄飞, 宁爱兵, 刘志民, 何咏梅, 王永斐, 张惠珍. 顶点加权最大团问题的加权分治算法[J]. 数学理论与应用, 2017, 37(2): 97-104.

Huang Fei , Ning Aibing, Liu Zhimin, He Yongmei , Wang Yongfei , Zhang Huizhen. Measure and Conquer Approach for the Maximum Vertex Weighted Clique Problem[J]. Mathematical Theory and Applications, 2017, 37(2): 97-104.

[1]	李波. 一类离散 Hindmarsh-Rose模型的分支延拓 [J]. 数学理论与应用, 2017, 37(3-4): 59-63.
[2]	屈珊珊, 王娟. 带移民和拯救的二次加权分枝过程的有关性质[J]. 数学理论与应用, 2017, 37(2): 11-17.
[3]	徐峰. 基于次分数布朗运动下广义交换期权的定价模型 [J]. 数学理论与应用, 2017, 37(2): 18-23.
[4]	倪念勇, 孙波. 基于全变分的图像去噪算法[J]. 数学理论与应用, 2017, 37(2): 32-37.
[5]	孙鹏飞, 杨卫国. 非齐次马氏链广义熵遍历定理的一个推广[J]. 数学理论与应用, 2017, 37(1): 44-49.
[6]	魏欣, 马良, 张惠珍. 多目标度约束最小生成树的蚁群优化算法求解[J]. 数学理论与应用, 2017, 37(1): 81-89.
[7]	王洁, 王波. 基于最小二乘法的GM(1,1)模型在我国蔬菜产量预测中的应用研究 [J]. 数学理论与应用, 2016, 36(4): 116-124.
[8]	周越. 部分信息下含债务的马氏调制收益率的最优投资组合问题[J]. 数学理论与应用, 2016, 36(3): 77-82.