团图点删除问题的近似算法

针对团图点删除问题的3-近似算法得到的近似解可能较大的问题,通过对团图点删除问题及团图特性的分析,提出了该问题的一个新的近似算法。新算法通过考察图中节点的一阶和二阶邻点来计算节点关联的P3的数目,然后优先选择P3数最大的节点加入解集,以期尽快消除图中的P3,从而最终获得较小的点删除集。为检验算法效果,设计了多组不同场景的随机实验对新算法和经典的3-近似算法进行了比较。随机实验表明,新算法较经典的3-近似算法有明显的优势。     

An effective local search for the maximum clique problem

We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.     

团数为5的零因子图对应的有限交换局部环

零因子图主要是利用图论的语言和工具来研究并解决代数中的一些难题。对于任意的有限交换局部环, 其代数结构一直是研究难点。通过对零因子图团数的分类, 讨论了当团数为5时, 对应的有限交换局部环R的代数性质, 刻画了环R的极大理想的幂零指数。特别是, 当极大理想的幂零指数为5时, 对极大理想的代数结构及极小生成元集进行了具体刻画。     

Integer Programming Model for Maximum Clique in Graph

The maximum clique or maximum independent set of graph is a classical problem in graph theory. Combined with Boolean algebra and integer programming, two integer programming models for maximum clique problem,which improve the old results were designed in this paper. Then, the programming model for maximum independent set is a corollary of the main results. These two models can be easily applied to computer algorithm and software, and suitable for graphs of any scale. Finally the models are presented as Lingo algorithms, verified and compared by several examples.     

基于遗传算法的近似最大连通分量的抽取算法

提出了一种基于遗传算法的近似连通图的抽取算法，通过定义编码、种群初始化方法和交叉变异修正使得遗传算法可以解决最大连通分量的抽取问题．为验证该算法，将该算法与RACLIQUE进行了比较．实验结果表明本文提出的算法在解MCP问题时，执行的速度受节点规模变化小，效率优于RACLIQUE算法．     

应用DNA计算解决最大团问题

DNA计算是应用分子生物技术进行计算的新方法。具有高度并行性、大容量、低能耗的特点。开创了以生物技术为工具解决复杂问题的新纪元,为解决NP完全问题开辟了一条新途径。本文主要介绍了DNA计算的基本思想及解决NP完全问题的DNA计算方法。     

Synchronization among neighbouring RNCs in a TD‐CDMA mobile network

In the paper, we use zone concepts, and also consider multiple‐bunch in a TD‐CDMA mobile network. In the multiple‐bunch environment, we need a synchronization mechanism to avoid inter‐RNC interferences. Here, we use an Informed‐of message to transmit local resource allocation results to other neighbouring RNCs through a high‐speed network. Thus, inter‐RNC interferences can be avoided and the global resource allocation can be made with the message passing. Within the resource allocation algorithm, we also find maximal compatible cliques to achieve the best resource utilization, using the graph algorithm finding maximal cliques in graph theory. Through the simulation, we found that the SRU classification using Conservative strategy matching the SRU allocation using Aggressive strategy has the best performance among all combinations. Copyright © 2006 John Wiley & Sons, Ltd.     

A new parallel tabu search algorithm for the optimization of the maximum vertex weight clique problem

The efficiency of metaheuristic algorithms depends significantly on the number of fitness value evaluations performed on candidate solutions. In addition to various intelligent techniques used to obtain better results, parallelization of calculations can substantially improve the solutions in cases where the problem is NP-hard and requires many evaluations. This study proposes a new parallel tabu search method for solving the Maximum Vertex Weight Clique Problem (MVWCP) on the Non-Uniform Memory Access (NUMA) architectures using the OpenMP parallel programming paradigm. Achieving scalability in the NUMA architectures presents significant challenges due to the high complexity of their memory systems, which can lead to performance loss. However, our proposed Tabu-NUMA algorithm provides up to $18\times$ speed-up with 64 cores for ten basic problem instances in DIMACS-W and BHOSLIB-W benchmarks. And it improves the performance of the serial Multi Neighborhood Tabu Search (MN/TS) algorithm for 38 problem instances in DIMACS-W and BHOSLIB-W benchmarks. We further evaluate our algorithm on larger datasets with thousands of edges and vertices from Network Data Repository benchmark problem instances, and we report significant improvements in terms of speed up. Our results confirm that the Tabu-NUMA algorithm is among the best recent algorithms for solving MVWCP on the NUMA architectures.     

复杂属性条件下基于Spark的clique社区搜索算法

现有的社区搜索算法难以在网络中找到满足给定复杂属性条件的社区。同时,随着网络规模的不断扩大,单机串行的社区搜索算法也已无法有效地处理大规模的网络数据。针对复杂属性条件下的clique社区搜索问题,提出一种基于Spark的搜索算法。在Spark并行计算框架的基础上,结合图的结构特征和内容属性,根据由布尔表达式定义的复杂属性条件采取不同的搜索策略,搜索时利用属性的搜索成本和扩展成本进行局部优化,从而加快搜索过程。实验结果表明,与结构优先或属性优先的社区搜索算法相比,该算法在不同属性条件、网络规模和节点数目的情况下均能保证搜索准确性并提高搜索效率。     

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

提出了关于最大团问题的一种新思路--基于平均度排序的局部枚举算法.对于一般的随机图G而言,图中含有最大团(d(G) 1)-团的概率要明显大于δ(G)-团或△-团.此算法通过了在随机图上进行实算的测试.实际计算结果表明:基于平均度排序的枚举算法比目前一般的基于枚举思想的算法更有效,其程序易于并行执行,值得进一步研究.