An Optimal Parallel Algorithm for Constructing a Spanning Tree on Proper Circle Trapezoid Graphs

Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.

Graph neural network-based scheduling for multi-UAV-enabled communications in D2D networks

In this paper,we jointly design the power control and position dispatch for Multi-Unmanned Aerial Vehicle(UAV)-enabled communication in Device-to-Device(D2D)networks.Our objective is to maximize the total transmission rate of Downlink Users(DUs).Meanwhile,the Quality of Service(QoS)of all D2D users must be satisfied.We comprehensively considered the interference among D2D communications and downlink transmissions.The original problem is strongly non-convex,which requires high computational complexity for traditional optimization methods.And to make matters worse,the results are not necessarily globally optimal.In this paper,we propose a novel Graph Neural Networks(GNN)based approach that can map the considered system into a specific graph structure and achieve the optimal solution in a low complexity manner.Particularly,we first construct a GNN-based model for the proposed network,in which the transmission links and interference links are formulated as vertexes and edges,respectively.Then,by taking the channel state information and the coordinates of ground users as the inputs,as well as the location of UAVs and the transmission power of all transmitters as outputs,we obtain the mapping from inputs to outputs through training the parameters of GNN.Simulation results verified that the way to maximize the total transmission rate of DUs can be extracted effectively via the training on samples.Moreover,it also shows that the performance of proposed GNN-based method is better than that of traditional means.

SGT-Net: A Transformer-Based Stratified Graph Convolutional Network for 3D Point Cloud Semantic Segmentation

In recent years,semantic segmentation on 3D point cloud data has attracted much attention.Unlike 2D images where pixels distribute regularly in the image domain,3D point clouds in non-Euclidean space are irregular and inherently sparse.Therefore,it is very difficult to extract long-range contexts and effectively aggregate local features for semantic segmentation in 3D point cloud space.Most current methods either focus on local feature aggregation or long-range context dependency,but fail to directly establish a global-local feature extractor to complete the point cloud semantic segmentation tasks.In this paper,we propose a Transformer-based stratified graph convolutional network(SGT-Net),which enlarges the effective receptive field and builds direct long-range dependency.Specifically,we first propose a novel dense-sparse sampling strategy that provides dense local vertices and sparse long-distance vertices for subsequent graph convolutional network(GCN).Secondly,we propose a multi-key self-attention mechanism based on the Transformer to further weight augmentation for crucial neighboring relationships and enlarge the effective receptive field.In addition,to further improve the efficiency of the network,we propose a similarity measurement module to determine whether the neighborhood near the center point is effective.We demonstrate the validity and superiority of our method on the S3DIS and ShapeNet datasets.Through ablation experiments and segmentation visualization,we verify that the SGT model can improve the performance of the point cloud semantic segmentation.

A Parallel Algorithm for the Spanning Forest Problem on Proper Circle Graphs

Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. In this paper, we present an?time parallel algorithm with processors for constructing a spanning forest on proper circle graph G on EREW PRAM.

Performance analysis of graph-based scheduling for device-to-device communications overlaying cellular networks

The performance of the graph-based scheduling for device-to-device communications overlaying cellular networks is studied. The graph-based scheduling consists of two stages, the frequency assignment stage and the time slot scheduling stage. For such scheduling, a theoretical method to analyze the average spectrum efficiency of the D2D subsystem is proposed. The method consists of three steps. First, the frequency assignment stage is analyzed and the approximate formula of the average number of the D2D links which are assigned the same frequency is derived. Secondly, the time slot scheduling stage is analyzed and the approximate formula of the average probability of a D2D link being scheduled in a time slot is derived. Thirdly, the average spectrum efficiency of the D2D subsystem is analyzed and the corresponding approximate formula is derived. Analysis results show that the average spectrum efficiency of the D2D subsystem is approximately inversely linearly proportional to the second- order origin moment of the normalized broadcast radius of D2D links. Simulation results show that the proposed method can correctly predict the average spectrum efficiency of the D2D subsystem.

单圈图的D(2)-点和可区别全染色

图G的D(2)-点和可区别全染色是指在图G的一个正常全染色φ下,G中任意两个距离不超过2的顶点u,v,其色集合中所有颜色数之和互不相同.使得G有一个k-D(2)-点和可区别全染色的最小整数k,称为图G的D(2)-点和可区别全色数.文中应用组合零点定理和权转移方法刻画了单圈图的D(2)-点和可区别全染色,并得到其D(2)-点和可区别全色数.

The Formation Control of Multi-agent Systems on a Circle

This paper investigates the formation control of a class of multi-agent systems moving on a circle, whose topology is a cyclic graph, and presents several new results for the following two cases: Case I, the agents with single-integrator kinematics,and Case II, the agents with double-integrator kinematics. Firstly,for Case I, two control protocols are proposed under which the multiagent systems keep a uniformly-spaced formation. Secondly,we study Case II, and a control protocol is designed for this case, then the stability of the formation is proved. Finally, three simulations are studied by using our presented results. The study of illustrative examples with simulations shows that our results as well as designed control protocols work very well in studying the formation control of this class of multi-agent systems.

GCR-Net:3D Graph convolution-based residual network for robust reconstruction in cerenkov luminescence tomography

Cerenkov Luminescence Tomography(CLT)is a novel and potential imaging modality which can display the three-dimensional distribution of radioactive probes.However,due to severe ill-posed inverse problem,obtaining accurate reconstruction results is still a challenge for traditional model-based methods.The recently emerged deep learning-based methods can directly learn the mapping relation between the surface photon intensity and the distribution of the radioactive source,which effectively improves the performance of CLT reconstruction.However,the previously proposed deep learning-based methods cannot work well when the order of input is disarranged.In this paper,a novel 3D graph convolution-based residual network,GCR-Net,is proposed,which can obtain a robust and accurate reconstruction result from the photon intensity of the surface.Additionally,it is proved that the network is insensitive to the order of input.The performance of this method was evaluated with numerical simulations and in vivo experiments.The results demonstrated that compared with the existing methods,the proposed method can achieve efficient and accurate reconstruction in localization and shape recovery by utilizing threedimensional information.

3D scene graph prediction from point clouds

Background In this study,we propose a novel 3D scene graph prediction approach for scene understanding from point clouds.Methods It can automatically organize the entities of a scene in a graph,where objects are nodes and their relationships are modeled as edges.More specifically,we employ the DGCNN to capture the features of objects and their relationships in the scene.A Graph Attention Network(GAT)is introduced to exploit latent features obtained from the initial estimation to further refine the object arrangement in the graph structure.A one loss function modified from cross entropy with a variable weight is proposed to solve the multi-category problem in the prediction of object and predicate.Results Experiments reveal that the proposed approach performs favorably against the state-of-the-art methods in terms of predicate classification and relationship prediction and achieves comparable performance on object classification prediction.Conclusions The 3D scene graph prediction approach can form an abstract description of the scene space from point clouds.

一类仙人掌图的D(2)-点可区别全染色

用数学归纳法和组合分析法给出最大度为3的仙人掌图G T的D(2)-点可区别全染色,进而得到χ_(2vt)(G T)≤6.结果表明,D(β)-VDTC猜想对最大度为3的仙人掌图成立.

图的L(d,1,1)-标号

给出了图L(d,1,1)-标号的一般性质.对一般图G,给出了构造L(d,1,1)-标号的一个算法,证明了λd,1,1(G)≤Δ3-Δ2+dΔ.对最大度Δ的树T,证明了d+Δ-1≤λd,1,1(T)≤d+2Δ-2,并且式中的上界与下界都是可达的.此外,对于两类特殊的树图:拟正则树TΔ及正则毛毛虫Catn,给出了确切的L(d,1,1)-标号数,其中d≥2.

基于偏差有向图和D-H方法的产品装配精度预测技术

装配精度预测对于产品装配精度保证具有重要意义。综合产品偏差源和偏差统一模型表达,提出偏差的旋量映射方法;在零件配合、双配合偏差传递分析的基础上,给出装配偏差有向图(Directed deviation graph,DDG)模型,并提出产品装配偏差有向图的构建流程。基于DDG模型,进一步研究用于装配精度累积的最小偏差路及其Dijkstra求解算法。在最小偏差路基础上,针对一维线性方向的装配精度预测,给出刚性零件装配偏差统计量的求解方法;针对多维空间方向的装配精度预测,提出借鉴并联机器人末端位姿计算的D-H(Denavit-hartenberg,D-H)方法,进行刚性零件装配偏差统计量的求解流程。基于装配偏差统计量,进一步给出产品装配精度评价指标,以及产品装配精度预测方法。以某产品的装配为例,介绍装配偏差统计量的求解及其装配精度预测过程。

概念格理论中的G-D基蕴涵约简研究

概念格理论中的G-D基是一个形式背景的最小蕴涵基,从G-D基中可以产生一个背景的所有蕴涵,对G-D基的研究对于数据挖掘和规则提取都有很重要的意义。当G-D基中的蕴涵很多时,从它推导出背景中的全部蕴涵就很困难,减小G-D基的尺寸能够节省很多时间。提出了利用概念层次图约简G-D基的尺寸,通过利用Armstrong公理系统比较说明了G-D基的尺寸变小后推导蕴涵的效率明显提高,并提出了恢复G-D基中的蕴涵的一种并行算法,该算法基于可约属性类对G-D基中的蕴涵进行恢复。

路和圈上的锥的D(2)-点可区别正常边染色

设G是顶点集合为V(G)={v0i|i=1,2,…,p}的简单图,n是正整数,称Mn(G)为G上的锥(或广义My-cielski图),如果V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp,w},E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤j,k≤p,i=0,1,…,n-1}∪{vnjw|1≤j≤p}。讨论了路和圈上的锥的D(2)-点可区别正常边染色,并给出了相应的色数。

基于相位差的均匀圆阵DOA估计新方法

根据均匀圆阵阵列结构的特点,提出一种利用相邻阵元间相位差进行二维波达方向(direction of ar-rival,DOA)估计的方法。分析了均匀圆阵相邻阵元间接收信号相位差的变化规律,得出了其与入射信号的方位角和俯仰角的对应关系,在此基础上推导出入射信号方位角和俯仰角的闭式解。同时,针对相位差测量中存在相位模糊的问题,提出一种循环搜索算法有效地实现了相位差的解模糊,极大地提高了利用相位差进行DOA估计的稳健性和适用范围。理论分析和仿真结果表明,该二维DOA估计方法可以在存在相位模糊的情况下稳健有效地工作。

应用多尺度三维图搜索的SD-OCT图像层分割方法

频谱域光学相干层析技术(SD-OCT)是一种广泛应用于眼科领域的成像技术,视网膜组织层分割对视网膜疾病诊断起着至关重要的作用。传统的三维图搜索方法能够同时分割k(k≥1)个三维面,但其存在时间复杂度高、分割病变图像鲁棒性弱等问题。在传统三维图搜索模型的基础上引入多尺度思想,提出应用多尺度三维图搜索的SDOCT视网膜图像分割方法。首先根据每个组织层的特点,为每层构造一个合理的顶点权重;然后利用相邻列的最大与最小高度差构造列约束限制,改进表面的平滑约束条件;最后利用低尺度的图像,应用三维图搜索方法进行粗分割,逐步向高一尺度应用三维图搜索方法进行单表面细分割。使用改进算法对3组正常眼睛及1组老年黄斑变性视网膜图像进行分割,并将结果与手动分割及传统三维图搜索方法进行比较,实验结果表明,改进算法能够准确有效地分割出3个层边界(边界位置绝对误差是3.86±2.50μm),并且接近于手动分割结果(3.78±2.76μm),优于传统三维图搜索方法(7.92±3.31μm)。

广义Petersen图的L(d,1)-标号

图G的顶点集到非负整数集的一个映射f满足:对任意的x,y∈V(G),当dG(x,y)=1时,有f(x)-f(y)≥d;当dG(x,y)=2时,有f(x)-f(y)≥1。图的一个k-L(d,1)-标号是指图的一个标号L(d,1)使得min{f(v)|v∈V(G)}=k,标号数简记为λd(G)。研究了广义的Petersen图的标号L(d,1),给出一个特殊的标号方法,得到了广义的Petersen图的标号数λd(G)≤4d。

无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法

无线传感器网络随节点移动组成自我维持的自组织系统,采用连通支配集的虚拟骨干技术可使平面网络系统层次化而简化节点路由、管理和维护。但大规模无线传感器网络的连通支配集节点数目依然庞大,d-hop连通支配集可以大大减小支配集节点数目。另外,由于存在节点失效、链路断裂等无线特性,虚拟骨干网需要具备一定的容错性。在单位圆盘图网络模型中为构建精简且具有容错能力的虚拟骨干网,提出d-hop 2-连通支配集的分布式构造算法,先构造d-hop独立支配集后再连通形成d-hop 2-连通支配集。并从理论和仿真上对算法的复杂度、近似比和算法性能作了进一步探讨和验证。

外平面图的L(d,1)-标号

研究外平面图G的L(d,1)-标号问题,证明了外平面图的L(d,1)-标号数满足:λd≤Δ+2(2d-1)。对于L(d,1)-标号问题有一著名猜想:对最大度为Δ的任意图有λ(G)≤Δ2,本论文证明了此猜想对外平面图是正确的。

基于D/S模式的水库防洪调度系统研究

针对我国水库防洪调度系统研究与应用的现状及存在问题,提出了基于D/S模式的水库防洪调度系统的解决方案,采用Java Web Start软件实现了D/S模式的整体架构、利用图论实现了水库群的集成,应用Hibernate框架解决了业务逻辑与数据库间强耦合关系,并利用设计模式增强了系统的可维护性和可复用性。