Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m...Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.展开更多
We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following a...We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following advantages: the frame of the algorithms is unified, the method is simple, and its implementation and revision are easy.展开更多
The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the...The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].展开更多
The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those re...The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .展开更多
We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero...We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.展开更多
基于图卷积神经网络(GCNN)的指静脉识别方法不仅可以解决传统指静脉识别方法识别率较低的问题,还可以解决其计算量大的问题。针对目前指静脉图模型结构不稳定和匹配效率因模型增大而下降的问题,采用SLIC(Simple Linear Iterative Cluste...基于图卷积神经网络(GCNN)的指静脉识别方法不仅可以解决传统指静脉识别方法识别率较低的问题,还可以解决其计算量大的问题。针对目前指静脉图模型结构不稳定和匹配效率因模型增大而下降的问题,采用SLIC(Simple Linear Iterative Clustering)超像素分割算法来构建加权图并改变GCNN提取加权图的图级特征。为了有效抓取图数据中的高阶特征并避免过平滑,建立一种双分支多交互的深度图卷积网络(GCN),旨在提升节点对高阶特征的掌握能力。首先根据节点特征对图结构进行调整;然后结合原始和重构后的图结构,构建了双分支网络架构以充分挖掘高阶特征;最后设计一种通道信息互动机制,以促进不同分支间的信息交流,从而提高特征的多样性。实验结果显示,在多个标准数据集上进行指静脉识别任务时,该网络能减少单张图片识别时间,提高识别效率,并有效减轻过平滑现象,相较于单分支的GCN,在识别精度上平均取得了超过1.5百分点的性能提升。展开更多
目的组合零样本识别是计算机视觉领域零样本学习任务的子任务,旨在从已经见过的组合图像中学习属性和物体概念,并将其迁移到未见过的组合上。现有方法对组合图像中属性和物体的解耦合能力不足,并且未能充分发挥文本标签对于属性和物体...目的组合零样本识别是计算机视觉领域零样本学习任务的子任务,旨在从已经见过的组合图像中学习属性和物体概念,并将其迁移到未见过的组合上。现有方法对组合图像中属性和物体的解耦合能力不足,并且未能充分发挥文本标签对于属性和物体信息的解耦合作用。方法为解决组合图像中属性与物体信息纠缠的问题,针对文本与视觉模态的差异,提出双模态解耦机制:在文本端构建图神经网络以建模属性与物体间的语义关系,在视觉端引入交叉注意力机制增强对属性和物体特征的分离能力。该方法集成于语言图像预训练框架中,从语言与视觉两个层面提升模型对属性与物体概念的建模能力,从而增强未见组合的识别效果。结果在3个主流的组合零样本识别基准数据集MIT-States、UT-Zappos和C-GQA(compositional GQA)上对所提方法进行了系统评估,结果表明模型性能显著提升。以MIT-States数据集为例,在封闭世界设置下,相较于性能排名第2的模型,本文方法的AUC(area under curve)提升3.3%,HM(Harmonic mean)提升2.4%,已见组合的识别准确率提升5.3%,未见组合提升1.0%;在开放世界设置下,本文方法的AUC提升0.9%,HM提升0.7%,已见组合与未见组合准确率分别提升3.2%和1.0%。此外,在MIT-States数据集上对提出的文本与视觉解耦模块及其上下文建模组件进行了消融实验,进一步验证了各子模块对整体性能的有效贡献。结论所提出的图文双端解耦合模块提升了模型对于组合中属性和物体的学习能力,显著提升了模型在组合零样本识别任务上的表现。展开更多
基金Supported by Changsha Natural Science Foundation(No.kq2208001)the Key Project Funded by Hunan Provincial Department of Education(No.21A0590)。
文摘Determining the crossing number of a given graph is NP-complete. The cycle of length m is denoted by Cm = v1v2…vmv1. G^((1))_(m) (m ≥ 5) is the graph obtained from Cm by adding two edges v1v3 and vlvl+2 (3 ≤ l ≤ m−2), G^((2))m (m ≥ 4) is the graph obtained from Cm by adding two edges v1v3 and v2v4. The famous Zarankiewicz’s conjecture on the crossing number of the complete bipartite graph Km,n states that cr(Km,n)=Z(m,n)=[m/2][m-1/2][n/2[n-1/2].Based on Zarankiewicz’s conjecture, a natural problem is to study the change in the crossingnumber of the graphs obtained from the complete bipartite graph by adding certain edge sets.If Zarankiewicz’s conjecture is true, this paper proves that cr(G^((1))_(m)+Kn)=Z(m,n)+2[n/2] and cr(G^((2))_(m)+Kn)=Z(m,n)+n.
文摘We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following advantages: the frame of the algorithms is unified, the method is simple, and its implementation and revision are easy.
基金This work is supported by the Key Project of the Education Department of Hunan Province of China (05A037)by Scientific Research Fund of Hunan Provincial Education Department (06C515).
文摘The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤n) is Z(m,n). where Z(m,n) = [m/2] [(m-1)/2] [n/2] [(n-1)/2](for and real number x, [x] denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤G. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is Z(9, n) + 12[n/2].
基金Supported by the Scientific Research Fund of Education Department of Hunan Province(08C518)
文摘The crossing number of cartesian products of paths and cycles with 5-vertex graphs mostly are known, but only few cartesian products of 5-vertex graphs with star K 1,n are known. In this paper, we will extent those results, and determine the crossing numbers of cartesian products of two 5-vertex graphs with star K 1,n .
文摘We introduce the triple crossing number, a variation of the crossing number, of a graph, which is the minimal number of crossing points in all drawings of the graph with only triple crossings. It is defined to be zero for planar graphs, and to be infinite for non-planar graphs which do not admit a drawing with only triple crossings. In this paper, we determine the triple crossing numbers for all complete multipartite graphs which include all complete graphs.
文摘基于图卷积神经网络(GCNN)的指静脉识别方法不仅可以解决传统指静脉识别方法识别率较低的问题,还可以解决其计算量大的问题。针对目前指静脉图模型结构不稳定和匹配效率因模型增大而下降的问题,采用SLIC(Simple Linear Iterative Clustering)超像素分割算法来构建加权图并改变GCNN提取加权图的图级特征。为了有效抓取图数据中的高阶特征并避免过平滑,建立一种双分支多交互的深度图卷积网络(GCN),旨在提升节点对高阶特征的掌握能力。首先根据节点特征对图结构进行调整;然后结合原始和重构后的图结构,构建了双分支网络架构以充分挖掘高阶特征;最后设计一种通道信息互动机制,以促进不同分支间的信息交流,从而提高特征的多样性。实验结果显示,在多个标准数据集上进行指静脉识别任务时,该网络能减少单张图片识别时间,提高识别效率,并有效减轻过平滑现象,相较于单分支的GCN,在识别精度上平均取得了超过1.5百分点的性能提升。
文摘目的组合零样本识别是计算机视觉领域零样本学习任务的子任务,旨在从已经见过的组合图像中学习属性和物体概念,并将其迁移到未见过的组合上。现有方法对组合图像中属性和物体的解耦合能力不足,并且未能充分发挥文本标签对于属性和物体信息的解耦合作用。方法为解决组合图像中属性与物体信息纠缠的问题,针对文本与视觉模态的差异,提出双模态解耦机制:在文本端构建图神经网络以建模属性与物体间的语义关系,在视觉端引入交叉注意力机制增强对属性和物体特征的分离能力。该方法集成于语言图像预训练框架中,从语言与视觉两个层面提升模型对属性与物体概念的建模能力,从而增强未见组合的识别效果。结果在3个主流的组合零样本识别基准数据集MIT-States、UT-Zappos和C-GQA(compositional GQA)上对所提方法进行了系统评估,结果表明模型性能显著提升。以MIT-States数据集为例,在封闭世界设置下,相较于性能排名第2的模型,本文方法的AUC(area under curve)提升3.3%,HM(Harmonic mean)提升2.4%,已见组合的识别准确率提升5.3%,未见组合提升1.0%;在开放世界设置下,本文方法的AUC提升0.9%,HM提升0.7%,已见组合与未见组合准确率分别提升3.2%和1.0%。此外,在MIT-States数据集上对提出的文本与视觉解耦模块及其上下文建模组件进行了消融实验,进一步验证了各子模块对整体性能的有效贡献。结论所提出的图文双端解耦合模块提升了模型对于组合中属性和物体的学习能力,显著提升了模型在组合零样本识别任务上的表现。
