基于FPGA的图着色问题求解

图着色问题是在满足相邻顶点不能分配相同颜色且颜色数最少的约束条件下,将图的顶点划分为不相交的集合,且每个集合中的顶点分配相同的颜色。由于图着色问题属于NP-完全问题,求解图着色问题的算法复杂度会随顶点个数的增加呈指数级增长。当顶点个数非常大时,通用处理器求解图着色问题的性能将会显著下降。因此,该文基于现场可编程逻辑门阵列(FPGA)实现求解图着色算法的专用硬件加速器。首先依据FPGA模块化的设计思路提出并实现了基于回溯法的图着色问题求解的硬件架构;其次分析了FPGA内部消耗资源与图着色顶点数之间的关系;最后利用通用异步收发传输器协议实现了通用处理器与FPGA的通信。实验结果表明,相比于在通用处理器上利用软件实现图着色算法,基于FPGA所实现的图着色算法运行时间减少了一个数量级。除此之外,FPGA内部消耗资源数与顶点个数呈线性关系,且每次迭代时FPGA运算所消耗的时间与顶点个数无关。     

基于图着色的事务调度算法的设计

将处理对象抽象转换为事务,对于事务的调度问题提出了基于图着色思想的算法.将事务以及之间的联系建立事务调度模型,同时等价地转化为图着色问题,通过对图中的顶点着色来实现具有冲突的事务的调度.与一般图着色处理方式不同的是,本算法思想采用了对节点进行着色的思想来实现事务调度.基于图着色的算法的设计与实现使多事务多冲突问题得到解决、并且最大程度满足事务执行所需各元素的特殊要求.     

基于图着色的大规模无人机群三维网络资源分配算法

为了解决大规模无人机集群组网中的网络资源有限、有效分配网络资源难度大的问题,本文针对任意对无人机收发节点构成的通信网络,联合考虑时域、频域、空域,提出了一种基于图着色的三维网络资源分配算法。具体的,本文利用方向回溯阵列天线在传统时频二维网络资源划分的基础上开辟空间维度,得到三维网络资源划分问题。为了解决该三维资源分配问题,本文首先将其建模为图着色问题,然后提出了启发式和贪婪式两种复杂度不同、适应场景也不同的图着色算法,并进一步设计了由着色结果到网络资源分配方案的映射算法。仿真结果验证了所提方法的有效性,相较于传统时分多址接入和时频二维资源分配而言,大大提高了吞吐量和传包成功率。      

用自适应图着色算法解决RFID阅读器冲突问题

建立了阅读器网络的图模型,阐述了阅读器网络拓扑结构固定和可随机改变情况下对解决阅读器冲突问题的不同要求。对于动态阅读器网络应用中的阅读器冲突问题,基于图着色方法提出了一种自适应分布式的颜色选择算法,这种算法能降低相邻阅读器冲突概率,并且使获得特定百分率的成功传输所需的总时隙数最少。     

基于采样的大规模图聚类分析算法

针对当前聚类方法（例如经典的GN算法）计算复杂度过高、难以适用于大规模图的聚类问题，本文首先对大规模图的采样算法展开研究，提出了能够有效保持原始图聚类结构的图采样算法（Clustering-structure Representative Sampling，CRS），它能在采样图中产生高质量的聚类代表点，并根据相应的扩张准则进行采样扩张.此采样算法能够很好地保持原始图的内在聚类结构.其次，提出快速的整体样本聚类推断（Population Clustering Inference，PCI）算法，它利用采样子图的聚类标签对整体图的聚类结构进行推断.实验结果表明本文算法对大规模图数据具有较高的聚类质量和处理效率，能够很好地完成大规模图的聚类任务.     

一种基于图论的RFID防冲突建模与优化方法

针对RFID系统的超高频段、多读写器的静态拓扑结构,研究了读写器冲突问题,并提出了一种图论的图着色算法与遗传算法相结合的防冲突干扰方法.该静态预定义算法对读写器冲突建立图论模型,将读写器时隙分配问题转化为图论模型的K-顶点着色问题,优化遗传算法并用于求解图的K-顶点着色问题,求得最小时隙数和最优时隙分配方案.最后将算法应用于算例.实验结果表明该方法可行、实用,能够有效地防止读写器冲突干扰.     

基于Hopfield网络的图的着色算法

应用Ｈｏｐｆｉｅｌｄ网络模型，系统地研究了图的正常ｋ－顶点着色，正常ｋ－边着色以及正常ｋ－全着色的具体算法，建立了相应的数学理论，改进了此领域内的某些工作。     

天线阵列方向图的一种数值综合算法

本文提出了一种新型阵列综合算法，目标方向图迭代算法。这种算法与现有的阵列综合方法不同，它通过对目标方向图的迭代来调整实际方向图的形状，是一种纯数值的阵列综合算法。这种算法适用于任意结构阵列的方向图综合，计算效率高，可以满足实际工程的需要。作为验证，本文综合了一些具有代表性的天线阵列，给出了计算结果，并对结果进行了讨论。     

天线阵列方向图的一种数值综合算法

本文提出了一种新型阵列综合算法，目标方向图迭代算法。这种算法与现有的阵列综合方法不同，它通过对目标方向图的迭代来调整实际方向图的形状，是一种纯数值的阵列综合算法。这种算法适用于任意结构阵列的方向图综合，计算效率高，可以满足实际工程的需要。作为验证，本文综合了一些具有代表性的天线阵列，给出了计算结果，并对结果进行了讨论。     

基于增强自适应原型重构模型的小样本图节点分类

现实中存在着许多图结构数据，但是在应用场景中时常面临着标注数据短缺的问题。由于图结构的独特性，传统的小样本学习方法无法直接迁移到非欧几里得空间的图领域。同时，适用于大规模标注数据集的图表示算法发展迅速，但是缺乏对标注数据极端匮乏情况下的处理。因此，将小样本学习算法和图表征算法进行高效融合才能有效解决图有关的小样本问题。基于此，提出了一种图小样本学习模型增强自适应原型重构模型(Enhanced Self-adaptive Prototype Rebuilt, ESPR),通过图网络编码器获得丰富的节点表征，改进了原始原型网络的框架中不可学习的无参数原型提取方式；引入自注意力机制进行自适应的原型学习与重构，实现了噪声抑制，并在4个公开图数据集上进行了实验。结果表明，所提出的模型在准确率和F1值上显著超过了Meta-GNN和GPN等经典模型。     

基于图论着色模型的频谱分配研究

认知无线电是可以感知外界通信环境的智能通信系统,其中的频谱分配技术是解决现在频谱资源匮乏、提高频谱利用率的一项热门研究.该文首先对认知无线电系统中基于图论着色的频谱分配模型及其数学符号描述进行介绍;然后对图论着色中的几种算法进行了详细研究并比较总结;最后简单阐述了现存的问题及其未来的发展趋势.     

基于DNA折纸术求解图的顶点着色问题的方法

该文基于DNA折纸术,设计了一个通过DNA折纸结构的自组装求解图的顶点着色问题的方法。利用DNA折纸术可以构建出具有特定形状的DNA折纸结构。这些结构可以用来编码图的顶点和边,由于这些结构具有粘性末端,因此可以通过特异的分子杂交组装成为代表了不同的图的顶点着色方案的高级结构。利用DNA-纳米颗粒共聚体的属性和电泳等实验方法,可以筛选出正确的符合条件的图的顶点着色方案。该方法是一种高度并行的方法,可以极大地降低求解图的顶点着色问题的复杂度。     

转移法色交换

将图Ｇ的着色由一种变为中一种，通常用Ｋｅｍｐｅ法以交换。但是，对于某些情况，用此法无效。针对这个问题，本文提出了一种转移法色交换，它适用于平面图着色，方法直观，清晰且有效。     

光网络中基于预定组播业务的资源优化

文章利用遗传算法安排光网络中预定组播业务的计算顺序,提出了优化业务顺序的分层图算法和点着色算法,并与按时间顺序安排业务的算法进行了比较.仿真表明,优化排序后,资源优化效果明显.在波长数的优化上,分层图算法比点着色算法性能更好.在分层图算法中,业务放置顺序的优化对组播树总链路数的减少也有一定帮助.     

基于图染色思想的RFID防冲突算法研究

针对射频识别技术(RFID)存在多个阅读器同时传输数据容易产生冲突的问题,提出了一种基于图染色理论的防止冲突的算法。该算法利用图的染色算法将可能存在冲突的阅读器染成不同的颜色,使得每种不相同的颜色不能同时获得相同的时隙,降低了多个阅读器同时传输数据产生冲突的可能性。分析表明:采用该算法明显地降低了阅读器之间的冲突率,同时得到最小的时隙数,提高了信道利用率,为RFID防冲突算法提供了一种新的解决方案,同时为基于TDMA的广播调度模式也提供了一种新的时隙分配方式。     

基于顺序图着色方法的地面数字电视频率指配

介绍了频率指配的数学模型和顺序图着色方法,并举例说明了顺序图着色方法在地面电视频率指配规划中的实际应用.     

Fixed preference channel assignment for cellular telephone systems

We describe a method of channel assignment for cellular telephone systems (in which a limited number of rearrangements are allowed) that gives good performance, controls rearrangements, and is easy to analyze. The method is based on an initial coloring of the interference graph, and channels are assigned to a cell of the network according to a preference list that depends on this coloring. We give a construction for such preference lists and prove that this construction is optimal