低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

最大团问题的改进遗传算法求解

最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。     

基于局部有限搜索的无向图近似最大团快速求解算法

无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。     

一种借助邻接矩阵求任意图最大团的方法

最大团问题是图论中重要的NPC问题。文章以一种新的方法,通过矩阵运算选择图上可能存在最大团的分支,进而实现求解最大团的问题。算法的每一个步骤都可以用成熟的并行方法替代。     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法．蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法,蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

大规模图例的最大团问题算法分析

最大团问题是一个经典的组合优化问题,在蛋白质功能推测、竞胜标确定、视频对象分割等领域有广泛的应用。随着图例规模的增大,最大团问题求解难度增加,常规图例最大团求解算法已逐渐被大规模图例最大团求解算法取代。介绍求解大规模图例最大团问题的技术支撑点,重点总结基于大规模图例的最大团问题算法,并在大数据计算背景下对融合单层图划分方法和多层图划分方法的MapReduce框架和Spark框架进行优缺点分析。此外,比较k-core方法与k-community方法的应用场景,从算法分类的角度总结不同类型算法的优缺点,对求解大规模图例最大团问题的确定型算法进行梳理,并对代表性的求解算法在公开数据集中的表现进行对比分析。基于分析结果,指出不同算法在求解大规模图例最大团问题时需要重点关注的方面,并展望了智能优化算法、分层式深度强化学习方法、图结构相变分析技术的未来研究方向。     

基于并行约束规划的最大团识别研究

为提高大数据平台下大规模图例的最大团问题求解效率,提出一种基于并行约束规划的最大团识别算法.通过BMT图划分策略将一个复杂图例分割为若干个可独立计算的子图,并将其分配给Spark集群中的计算节点,每个计算节点采用约束规划方法对分割产生的子问题分别进行建模和求解,实现最大团问题的并行化处理.引入时间预测模型,设计基于任务运行时间预测模型的并行图划分方法,从而有效解决计算节点的负载均衡问题.实验结果表明,与基于BMC图划分策略的最大团并行识别算法相比,该算法具有更高的求解效率,可取得近似线性的加速比.     

一种改进的最大团问题DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n）,同时文中算法还具有高效的空间利用率及容错能力的优点．     

图论中最大独立集问题的精确算法

独立集问题是图论和组合数学中常见的NP-hard问题,在许多领域都有着重要的应用。分支降阶是目前广泛用于设计精确算法求解NP-hard问题的技术之一,主要通过快速降阶、分支及递归求解原问题及其子问题。针对图论中最大独立集问题设计了一个分支降阶算法,并通过增加快速降阶规则来降低算法的时间复杂度,最终通过分析得出一个时间复杂度为[O(1.285n)]的精确算法,该算法在理论上得到了一般图的最大独立集的最优解。     

最大团问题的改进蚁群算法求解

为了更好的解决最大团问题,提出一种改进的蚁群算法。通过提取图的顶点信息,将图用信息素模型来表示;根据最大团问题的约束条件利用蚁群构造极大团,并进行实时的全局信息素更新和局部信息素更新,直到找到最大团。实验结果表明,算法能较好的实现最大团问题,算法性能高于通用的蚁群算法。     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

A DNA-based algorithm for arranging weighted cliques

A fundamental idea and realization of networks arises in a variety of areas of science and engineering. Their theoretical underpinnings stem from graph theory where numerous fundamental concepts being formulated and solved there have become of immediate interest at the applied side. In this study, our focus is on the weighted maximum clique problem, a highly challenging problem in graph theory. The essence of the problem is to find the nodes with the maximum total of weights in a graph where an edge connects every pair of nodes, meaning every node connects to every other node. We propose an algorithm to find all the weighted cliques as well as the weighted maximum clique in order of size using the framework of DNA computing.     

New analytical lower bounds on the clique number of a graph

This paper proposes three new analytical lower bounds on the clique number of a graph and compares these bounds with those previously established in the literature. Two proposed bounds are derived from the well-known Motzkin–Straus quadratic programming formulation for the maximum clique problem. Theoretical results on the comparison of various bounds are established. Computational experiments are performed on random graph models such as the Erdös-Rényi model for uniform graphs and the generalized random graph model for power-law graphs that simulate graphs with different densities and assortativity coefficients. Computational results suggest that the proposed new analytical bounds improve the existing ones on many graph instances.     

基于三角环的顶点着色问题解法

图的着色问题是一个NP难问题,本文着重探讨无向图的顶点的三色问题,提出了用构造三角环的极大独立集方法判断并尝试给出顶点三色问题的可行解,解决了顶点三色的可满足性问题,克服了以前图遍历过程中的回溯问题,以及由此推论顶点四色和五色问题的极大独立集。