For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, ...For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.展开更多
The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) t...The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.展开更多
The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit desi...The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.展开更多
In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for ...In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for a large class of graphs, this new model will provide better solutions than the original circular chromatic number. At the same time, it allows us to avoid the difficulty of implementation when the fractional chromatic number is used.展开更多
大部分现有的用于预测环状RNA(circRNA)与疾病之间关联关系的计算模型通常使用circRNA和疾病相关数据等生物学知识,配合已知的circRNA-疾病关联信息对来挖掘出潜在的关联信息。然而这些模型受已知关联构成的网络稀疏性、负样本过少等固...大部分现有的用于预测环状RNA(circRNA)与疾病之间关联关系的计算模型通常使用circRNA和疾病相关数据等生物学知识,配合已知的circRNA-疾病关联信息对来挖掘出潜在的关联信息。然而这些模型受已知关联构成的网络稀疏性、负样本过少等固有问题的影响,导致预测性能不佳。因此,在图自动编码器基础上引入归纳式矩阵补全及自注意力机制进行二阶段融合,以实现circRNA-疾病关联预测,由此构建的模型叫GIS-CDA(Graph auto-encoder combining Inductive matrix complementation and Self-attention mechanism for predicting Circ RNA-Disease Association)。首先,计算circRNA集成和疾病集成的相似性,并利用图自动编码器学习circRNA和疾病的潜在特征,以获得低维表征;接着,将学习到的特征输入归纳式矩阵补全,以提高节点之间的相似性和依赖性;然后,将circRNA特征矩阵和疾病特征矩阵整合为circRNA-疾病特征矩阵,以增强预测的稳定性和精确性;最后,引入自注意力机制,从特征矩阵中提取重要特征,并减少对其他生物信息的依赖。五折交叉和十折交叉验证的结果显示:GIS-CDA获得的平均接收者操作特征曲线下面积(AUROC)值分别为0.9303和0.9393,前者比基于KATZ测度的人类circRNA-疾病关联预测模型(KATZHCDA)、基于深度矩阵分解方法的circRNA-疾病关联(DMFCDA)预测模型、RWR(Random Walk with Restart)和基于加速归纳式矩阵补全的circRNA-疾病关联(SIMCCDA)预测模型分别高出了13.19、35.73、13.28和5.01个百分点;GIS-CDA的精确率-召回率曲线下面积(AUPR)值分别为0.2271和0.2340,前者比上述对比模型分别高出了21.72、22.43、21.96和13.86个百分点。此外,在circRNADisease、circ2Disease和circ R2Disease数据集上的消融实验和案例研究进一步验证了GIS-CDA在预测circRNA-疾病的潜在关联方面具有较好的性能。展开更多
基金the National Natural Science Foundation of China under Grant No.10671073Scientific Study Foundation of the Talented People Gathered by Nantong University+2 种基金Science and Technology Commission of Shanghai Municipality under Grant No.07XD14011Shanghai Leading Academic Discipline Project under Grant No.B407Natural Science Foundation of Jiangsu's Universities under Grant No.07KJB110090
文摘作者为一张圆形的图的射影的飞机十字路口数字给上面的界限。另外，作者证明圆形的图 C (8,3 ) 和 C (9,3 ) 的射影的飞机十字路口数字分别地是 2 和 1。
基金Supported by National Science Foundation of China (10371048)the Science Foundation of Three Gorges University.
文摘For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.
文摘The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.
文摘The feedback vertex set (FVS) problem is to find the set of vertices of minimum cardinality whose removal renders the graph acyclic. The FVS problem has applications in several areas such as combinatorial circuit design, synchronous systems, computer systems, and very-large-scale integration (VLSI) circuits. The FVS problem is known to be NP-hard for simple graphs, but polynomi-al-time algorithms have been found for special classes of graphs. The intersection graph of a collection of arcs on a circle is called a circular-arc graph. A normal Helly circular-arc graph is a proper subclass of the set of circular-arc graphs. In this paper, we present an algorithm that takes time to solve the FVS problem in a normal Helly circular-arc graph with n vertices and m edges.
文摘In this article we propose a new model for scheduling periodic tasks. The model is based on a variation of the circular chromatic number, called the multiple circular colouring of the conflict graph. We show that for a large class of graphs, this new model will provide better solutions than the original circular chromatic number. At the same time, it allows us to avoid the difficulty of implementation when the fractional chromatic number is used.
文摘大部分现有的用于预测环状RNA(circRNA)与疾病之间关联关系的计算模型通常使用circRNA和疾病相关数据等生物学知识,配合已知的circRNA-疾病关联信息对来挖掘出潜在的关联信息。然而这些模型受已知关联构成的网络稀疏性、负样本过少等固有问题的影响,导致预测性能不佳。因此,在图自动编码器基础上引入归纳式矩阵补全及自注意力机制进行二阶段融合,以实现circRNA-疾病关联预测,由此构建的模型叫GIS-CDA(Graph auto-encoder combining Inductive matrix complementation and Self-attention mechanism for predicting Circ RNA-Disease Association)。首先,计算circRNA集成和疾病集成的相似性,并利用图自动编码器学习circRNA和疾病的潜在特征,以获得低维表征;接着,将学习到的特征输入归纳式矩阵补全,以提高节点之间的相似性和依赖性;然后,将circRNA特征矩阵和疾病特征矩阵整合为circRNA-疾病特征矩阵,以增强预测的稳定性和精确性;最后,引入自注意力机制,从特征矩阵中提取重要特征,并减少对其他生物信息的依赖。五折交叉和十折交叉验证的结果显示:GIS-CDA获得的平均接收者操作特征曲线下面积(AUROC)值分别为0.9303和0.9393,前者比基于KATZ测度的人类circRNA-疾病关联预测模型(KATZHCDA)、基于深度矩阵分解方法的circRNA-疾病关联(DMFCDA)预测模型、RWR(Random Walk with Restart)和基于加速归纳式矩阵补全的circRNA-疾病关联(SIMCCDA)预测模型分别高出了13.19、35.73、13.28和5.01个百分点;GIS-CDA的精确率-召回率曲线下面积(AUPR)值分别为0.2271和0.2340,前者比上述对比模型分别高出了21.72、22.43、21.96和13.86个百分点。此外,在circRNADisease、circ2Disease和circ R2Disease数据集上的消融实验和案例研究进一步验证了GIS-CDA在预测circRNA-疾病的潜在关联方面具有较好的性能。
