若干最大松弛团问题的精确算法和应用研究

论文摘要

一个团（clique）是一个任何两个顶点都相邻的完全图。在社交网络中,完全图代表着最为紧密的社交关系,因此在网络中挖掘出最大的一个团非常有现实意义,也成为了社会计算、数据挖掘等领域中的一个经典问题。但是由于团的要求非常严格,为了更好地刻画密集子群结构,各种松弛团模型被提出。这些模型常通过对团的某一方面性质进行松弛得到,比如对顶点度数进行松弛得到的模型有k-core,k-plex等;对路由长度进行松弛得到的模型有k-clique,k-club等;对连通度进行松弛得到模型有k-block,k-bundle等。其中k均是模型固有的参数。最大松弛团问题,即从给定的图中提取基数最大的满足松弛团定义的子图,是著名的组合优化问题最大团的推广。本文将研究三个与最大松弛团相关的问题,一是最大k-plex问题,二是最大k-bundle问题,三是最小染色和（Minimum Sum Coloring）问题。本文首先研究了最大k-plex问题,并提出了一个基于分支定界的精确求解算法。相较于已有的最大k-plex问题的精确算法,本文从理论上分析证明了我们的算法具有更低的时间复杂度上界,是第一个突破2n时间复杂度的精确算法,其中n是图中的顶点数量。实验表明我们的算法在标准测试集上的表现也更优秀。接着本文研究了基于连通度松弛的模型k-bundle。针对最大k-bundle问题,我们分析了k-plex与k-bundle在结构上的异同,借鉴并改进了我们在最大k-plex问题的精确算法中提出的分支规则。同时本文还设计了更多基于直径,图染色等方法的剪枝规则用于加速我们的算法。在标准测试集上的实验对比表明,我们的算法相较于该问题已有的精确算法更高效,特别是在大规模的社交网络算例上。最后,本文给出了最大松弛团问题在最小染色和问题上的一个应用。最小染色和问题是在超大规模集成电路设计以及资源分配调度等领域有广泛应用一个的组合优化问题,本文给出了一个利用最大团和最大松弛团来构造最小染色和理论下界的方法。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究工作的背景及意义
•   1.2 国内外研究现状
•     1.2.1 最大k-plex问题
•     1.2.2 最大k-club问题
•     1.2.3 最大k-bundle问题
•     1.2.4 最小染色和问题
•   1.3 本文主要贡献与创新
•   1.4 论文结构安排
• 第二章 松弛团的定义和基本性质
•   2.1 符号和术语
•   2.2 朴素松弛团
•   2.3 二分团与二分松弛团
•   2.4 遗传性质
•   2.5 本章小结
• 第三章 最大k-plex问题的精确算法
•   3.1 问题定义及性质
•   3.2 分支规则
•   3.3 分支定界算法
•   3.4 实验结果
•   3.5 本章小结
• 第四章 最大k-bundle问题的精确算法
•   4.1 问题定义
•   4.2 遗传性及复杂度
•   4.3 规约规则
•   4.4 分支规则
•   4.5 分支定界算法
•   4.6 实验结果
•     4.6.1 随机图
•     4.6.2 第二届DIMACS图
•     4.6.3 SNAP和第十届DIMACS图
•     4.6.4 搜索树比较
•   4.7 本章小结
• 第五章 基于二分松弛团的最小染色和问题下界分析
•   5.1 问题定义及性质
•   5.2 已知理论下界回顾
•     5.2.1 Kokosínski和 Kwarciany提出的下界
•     5.2.2 Lecat等人提出的下界
•   5.3 新理论下界
•     5.3.1 新下界I
•     5.3.2 新下界II
•   5.4 实验结果
•   5.5 本章小结
• 第六章 总结与展望
•   6.1 全文总结
•   6.2 后续工作展望
• 致谢
• 参考文献
• 攻读硕士学位期间取得的成果

文章来源

类型: 硕士论文

作者: 林维博

导师: 肖鸣宇

关键词: 最大松弛团,精确算法,分支定界,组合优化,最小染色和

来源: 电子科技大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,计算机软件及计算机应用

单位: 电子科技大学

分类号: TP301.6;O157.5

总页数: 78

文件大小: 2354K

下载量: 38