基于图神经网络的多维度池化图分类

目前很多处理图数据的图神经网络方法被提出,然而大多数研究侧重于对特征聚合的卷积层的研究而不是进行下采样的池化层.此外,形成聚类簇的池化方式需要额外计算分配矩阵;节点得分的池化方式排名方式单一.为解决上述问题,提高图分类任务的准确性,本文提出了一种新的基于多维度信息的图池化算子MDPool.该模型使用节点特征信息以及图拓扑结构信息,获取不同维度下的节点得分.使用注意力机制归纳不同维度下的得分权重,生成更为健壮的节点排名,基于节点排名自适应选择节点集合生成诱导子图.提出的MDPool可以集成到多种的图神经网络结构,将MDPool池化算子与图神经网络卷积层堆叠形成编码解码模型EDMDPool.在4个公开数据集的图分类任务中, EDMDPool均高于现有基线模型.

图顶点着色问题的DNA粘贴算法

利用DNA粘贴模型的巨大并行性,从图顶点着色问题的本质出发,先把着色问题分解成顶点独立集问题和顶点划分问题并给出这两个问题的DNA粘贴算法,然后调用这两个算法解决了图顶点着色问题。实例证明DNA粘贴算法在理论上可以实现的。

若干图类的邻强边染色

研究了若干图类的邻强边染色 .利用在图中添加辅助点和边的方法 ,构造性的证明了对于完全图 Kn和路 Lm 的笛卡尔积图 Kn× Lm,有χ′as(Kn× Lm) =△ (Kn× Lm) +1 ,其中△ (Kn× Lm)和χ′as(Kn× Lm)分别表示图 Kn× Lm的最大度和邻强边色数 .同理验证了 n阶完全图 Kn的广义图 K(n,m)满足邻强边染色猜想 .

图的最小顶点覆盖问题的质粒DNA计算模型

给出了图的最小顶点覆盖问题的质粒DNA计算模型及其实现算法 .算法的时间复杂性是O(q) ,编码最小覆盖问题所需的核苷酸片段种类为n ,其中n ,q分别是图的规模和边数 .在算法中 ,所用酶的种类也等于图的规模 .而且 。

DNA Golay码的设计与分析

DNA编码是DNA计算初始数据库中寡核苷酸序列的设计问题.合理的DNA编码可以提高实验的稳定性和正确性,从而确保DNA计算的成功率.本文给出DNA码字重量和DNA码字间Watson-Crick Hamming距离的定义;提出DNA Golay码的设计方法;分析了DNA Golay码的性质和规模;与随机搜索优码方法相比,DNA Golay码求解优码更加简单可行.

图的最小顶点覆盖问题的面上DNA解法

1994年 ,Adlem an提出一种解决 NP完全问题的新方法— DNA计算 .之后又出现了许多关于 DNA计算的改进操作并增加了其可靠性 ,其中面上操作是一种很有效的方法 .本文利用 DNA计算的固态处理 (面上计算 )解决了图论中又一 NP完全问题—图的最小顶点覆盖问题 .构造了含有 6个顶点 10条边的图的顶点集子集对应的数据池之后 ,进行了一系列的合成、杂交、清洗、变性等生物操作 ,得到所有覆盖对应的 DNA序列 ,然后通过编址过程得到所要求的最小覆盖 .

基于剪接系统的有向哈密顿路问题分析

首先给出了剪接系统模拟有向哈密顿路问题的思想;然后通过此剪接系统所产生语言的性质对有向哈密顿路问题进行分析,给出了有向图存在哈密顿路的充要条件.在我们的构造中,模拟问题的剪接系统至多运行n-2步,其中n是模拟问题的规模.

基于粘贴和删除系统的图着色问题分析(英文)

图着色问题是图与组合优化中的一个NP-完全问题.现有算法在求解图着色问题时,计算复杂性随着待解问题规模的增大呈指数增长.粘贴系统和删除系统是分别基于粘贴运算和删除运算的两种语言生成器.文中将图着色问题和图的坏边数结合起来,将图着色问题转化成搜索最长序列的问题,然后利用粘贴系统和删除系统的并行性,得到了图的色数及其所有色类.与已有求解图着色问题的DNA算法相比,新的算法具有较低的复杂性.

广义图K(n,m)的全色数(英文)

196 5年 ,M.Behzad和 Vizing分别提出了著名的全着色猜想 :即对于简单图 G有 :XT( G)≤Δ + 2 ,其中Δ是图 G的最大度 .本文确定了完全图 Kn的广义图 K( n,m)的全色数 ,并利用它证明了 Lm× Kn( m≥ 3)是第 I型的 .

系列平行图的边色数

Vizing( 1 96 4年 )和Gupta( 1 96 6年 )各自独立地证明了边着色中的重要定理 :对任何简单图G ,有χ′(G) =Δ或 χ′(G) =Δ + 1。但确定一个图G的边色数仍是一个尚未解决的问题。本文利用系列平行图的结构性质 。

用混合遗传算法求解图的邻强边着色问题

图的邻强边着色算法是一个NP完全问题。提出了图的邻强迫着色问题的混合遗传算法。在设计交叉、变异方式时,将两点交叉与局部扫描结合起来,避免了种群的退化,从而有利于快速找到最好的解域。根据实际情况,将图的结构性质和迭代次数结合起来,巧妙地设计了算法的终止条件。实验仿真结果表明,混合遗传算法可以获得问题高质量的解,即对图进行邻强边着色所使用的颜色数接近图的邻强边色数。

图的最大平均度与关联色数(英文)

图G的关联着色是从关联集I(G)到颜色集C的一个映射使得任意两个相邻的关联不着同色。从图的结构性质出发,对图的关联着色进行了讨论,利用归纳法和换色技巧证明了mad(G)<3,Δ(G)=4的图G存在一个(6,2)-关联着色。

高度图的关联色数

为了解决强边着色猜想 ,1993年 ,Brualdi和Massey(DiscreteMath .(12 2 ) 5 1- 5 8)引入了关联着色概念 .陈东灵等[2 ] 证明了对于△ (G) =n- 2的图G ,inc(G) △ (G) + 2 ,其中n是G的阶数 .本文将进一步探讨在什么条件下 ,它的关联色数肯定是△ (G) + 1,又在什么条件下 ,肯定是△ (G) + 2 .

低度系列平行图的邻点可区别全染色

设G是阶数不小于2的简单连通图,G的k-正常全染色σ称为是邻点可区别的,如果对G的任意两个相邻顶点,它们的顶点及关联边的颜色构成的集合不同.满足上述条件的最小k称为是G的邻点可区别全色数.文中从系列平行图的结构性质出发,利用换色技巧、归纳法以及组合方法对最大度不大于7的系列平行图的邻点可区别全染色进行了研究.得到了当低度系列平行图中不含相邻最大度点时,其邻点可区别全色数是最大度加1,否则,其邻点可区别全色数的上界为最大度加3.

关于欧拉图的一个猜想的新结果

证明了非平面欧拉图在边连通度满足一定条件下可以表示成不超过｜Ｖ｜－２个边不重的圈的并，其中｜Ｖ｜是图的顶点数。

面向顺序存储结构的数据流分析

C程序中数组、malloc动态分配后的连续内存等顺序存储结构被大量使用,但大多数传统的数据流分析方法未能充分描述其结构及其上的操作,特别是在利用指针访问顺序存储结构时,传统的分析方法只关注了指针的指向关系,而未讨论指针可能发生偏移的数值信息,且未考虑发生偏移时可能存在越界的不安全问题,导致了对顺序存储结构分析不精确.针对以上不足,首先对顺序存储结构进行抽象建模,并对顺序存储结构与指针结合使用时的指向关系与偏移量进行有效表示,建立了用于顺序存储结构的抽象内存模型SeqMM;其次,归纳总结C程序中顺序存储结构涉及的指针相关迁移操作、谓词操作及遍历顺序存储结构的循环操作,提出了安全范围判别保证操作安全性;之后,针对函数调用时形参指针引用顺序存储结构与实参的映射过程进行过程间推导规则设计;最后,基于上述分析,提出了一种内存泄漏缺陷检测算法,对5个开源C工程的内存泄漏缺陷进行检测.实验结果表明,所提出的Seq MM能够有效地刻画C程序中的顺序存储结构及其涉及的各种操作,其数据流分析结果能够用于内存泄漏的检测工作,同时在效率和精度之间取得合理的权衡.

基于符号表达式的程序语义缺陷警报关联识别方法

针对程序静态缺陷检测存在高误报需要耗费大量人力消除的问题,提出了一种程序语义缺陷警报关联的方法,通过挖掘警报间的深层次关联信息建立警报关联,有助于提升人工判定警报的效率。首先采用符号表达式与区间表示一个变量的取值,并基于符号表达式的逻辑关系建立了警报间的关联推导规则,然后在缺陷检测阶段根据缺陷触发条件识别出警报并推导出不同警报间的关联,最后根据警报间的关联关系对警报进行自动判定。通过对5个实际C工程的测试结果表明,本文所提方法可以有效识别出警报间的关联关系,能够有效减轻人工判定警报的工作。

最大匹配问题的DNA表面计算模型

本文给出了一个最大匹配问题的DNA表面计算模型 ,我们在表面上逐步生成解空间的同时 ,利用酶切技术删除所产生的“不可行解” ,从而大大减少了最终生成的解空间 .最后 ,我们还研究了边的排列顺序对解空间的生成过程的影响 .结果表明 ,通过对图中的边进行合理的编排也能减小不可行解的生成 .

DNA计算中的编码方法研究

DNA计算是一种利用生物大分子间的相互作用来实现并行计算的新的计算模式。因为其具有强大的并行性和高密度的信息存储能力,因而引起了科学界的广泛关注。编码是DNA计算的第一步,也是最重要的一步。编码质量的好坏直接影响反应过程的速度和效率。论文主要介绍了DNA计算过程中的编码问题、影响编码的因素及已有的几种主要的编码方法;最后指出了DNA计算的编码方法存在的问题及研究方向。

DNA计算中荧光技术的应用及其发展

DNA计算作为前沿科学研究的重点和热点,已经从简单发展为复杂,从理论转化为应用.在这一过程中,反应速度快、变化灵敏的荧光标记技术发挥了重要的作用.文中围绕DNA计算和荧光标记技术两个方面进行说明.一方面,对近年来DNA计算中荧光技术的应用进行了总结:(1)荧光标记的表面计算;(2)与某些酶切技术相结合的荧光检测;(3)与DNA链置换相结合的荧光技术;(4)与基因沉默技术相结合的荧光DNA逻辑门;(5)与DNA自组装立体结构相结合的荧光技术;(6)与DNA变构相结合的荧光技术.另一方面,介绍了几种近年来发展起来的新型荧光技术:(1)荧光信号识别放大技术;(2)与磁珠技术相结合的荧光技术;(3)与PH值变化相结合的DNA荧光技术;(4)与miRNAs检测相结合的荧光技术.在今后的研究中,只有将这两者紧密结合,才能发挥DNA计算天然的优势.