SOLVING MINIMUM SPANNING TREE PROBLEM WITH DNA COMPUTING

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.

MINIMUM CONGESTION SPANNING TREES IN BIPARTITE AND RANDOM GRAPHS

The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.

Brain Functional Network Based on Small-Worldness and Minimum Spanning Tree for Depression Analysis

Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression,this paper proposes a depression analysis method based on brain function network(BFN).To avoid the volume conductor effect,BFN was constructed based on phase lag index(PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness(SW)characteristics and binarization BFN based on the minimum spanning tree(MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram(EEG)data of 24 patients with depression and 29 healthy controls(HC)was used to verify our proposed method.The results showed that compared with HC,the information processing of BFN in patients with depression decreased,and BFN showed a trend of randomization.

High-resolution Remote Sensing Image Segmentation Using Minimum Spanning Tree Tessellation and RHMRF-FCM Algorithm

It is proposed a high resolution remote sensing image segmentation method which combines static minimum spanning tree(MST)tessellation considering shape information and the RHMRF-FCM algorithm.It solves the problems in the traditional pixel-based HMRF-FCM algorithm in which poor noise resistance and low precision segmentation in a complex boundary exist.By using the MST model and shape information,the object boundary and geometrical noise can be expressed and reduced respectively.Firstly,the static MST tessellation is employed for dividing the image domain into some sub-regions corresponding to the components of homogeneous regions needed to be segmented.Secondly,based on the tessellation results,the RHMRF model is built,and regulation terms considering the KL information and the information entropy are introduced into the FCM objective function.Finally,the partial differential method and Lagrange function are employed to calculate the parameters of the fuzzy objective function for obtaining the global optimal segmentation results.To verify the robustness and effectiveness of the proposed algorithm,the experiments are carried out with WorldView-3(WV-3)high resolution image.The results from proposed method with different parameters and comparing methods(multi-resolution method and watershed segmentation method in eCognition software)are analyzed qualitatively and quantitatively.

THE DESIGN AND ANALYSIS OF ALGORITHM OF MINIMUM COST SPANNING TREE

This paper provides a method of producing a minimum cost spanning tree (MCST) using set operations. It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm. This algorithm uses the FDG (formula to divide elements into groups) to sort (the FDG sorts a sequence of n elements in expected tir O(n)) and uses the method of path compression to find and to unite. Therefore. n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).

A Novel Binary Firefly Algorithm for the Minimum Labeling Spanning Tree Problem

Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.

The Design of the Minimum Spanning Tree Algorithms

Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning trees. It designs the corresponding fitness function,operator and few controlling strategies to improve its speed and evolutionary efficiency.Only one solution can be gotten with running traditional al-gorithem atone time.The new algorithm can get a set of the solutions with higher probability in a shorter time.The experiment shows that it has a better performance than traditional methods.

On the Minimum Spanning Tree Determined by n Points in the Unit Square

Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.

Salience adaptive morphological structuring element construction method based on minimum spanning tree

Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,its shape may be changed and part of the information may be lost.Therefore,we propose a method for constructing salience adaptive morphological structuring elements based on minimum spanning tree(MST).First,the gradient image of the input image is calculated,the edge image is obtained by non-maximum suppression(NMS)of the gradient image,and then chamfer distance transformation is performed on the edge image to obtain a salience map(SM).Second,the radius of structuring element is determined by calculating the maximum and minimum values of SM and then the minimum spanning tree is calculated on the SM.Finally,the radius is used to construct a structuring element whose shape and size adaptively change with the local features of the input image.In addition,the basic morphological operators such as erosion,dilation,opening and closing are redefined using the adaptive structuring elements and then compared with the classical morphological operators.The simulation results show that the proposed method can make full use of the local features of the image and has better processing results in image structure preservation and image filtering.

基于最小Spanning树的中继节点部署算法

在能量受限的无线传感器网络(WSNs)中,部署中继节点成为确保通信覆盖的常用方法。提出基于最小Spanning树的中继节点部署算法(MST-DRN)。MST-DRN算法引用基于无线充电的能量模型。再依据节点的能量采集率计算边权值。依据边权值的图模型构建最小Spanning树(MST)。检测MST中不满足生存条件的非支叶节点,在节点附近部署中继节点,维持网络连通。实验数据表明:提出的MST-DRN算法在确保网络连通时,减少了成本(中继节点数),并提高了数据包传递率。

基于群论的频率图在旅行商问题中的应用

针对最小生成树(minimum spanning tree,MST)和旅行商问题(travelling salesman problem,TSP),介绍了完全图上的两类特殊图并定义了这些图上的交运算,每类特殊图和交运算构成一个半群。根据半群性质计算出频率图,分析了最优哈密顿圈(optimal Hamiltonian cycle,OHC)和MST中边的频率性质,证明了频率图上OHC中边的频率下界,该频率下界用于缩小OHC的搜索空间,降低了TSP的求解难度。此外,采用一些TSP算例验证了频率图上OHC中边的频率性质。

最小生成树的prim算法及minimum函数

本文介绍了最小生成树的prim算法,minimum函数的实现过程及该函数对由prim算法所得到的最小生成树的影响。

NeuroPrim:An attention-based model for solving NP-hard spanning tree problems

Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.

基于R^＊-tree的散乱点云截面数据获取算法

为快速准确地获取散乱点云的截面数据,以较少数据准确表达模型信息,提出一种截面数据获取算法.采用R*-tree建立点云的动态空间索引结构,基于该结构快速准确获取截面邻域数据,依据该数据与截平面的位置关系将邻域数据分为正负两个邻域,通过对两邻域数据点配对连线与截平面求交获取截面数据,并采用最小生成树算法对其排序,最终得到有序的截面数据.结果表明,该算法数据适应性强,截面数据获取精度高,运行速度快,且能够以较少数据准确表达模型型面特征.

MTree_Nix网络模拟路由策略的研究与优化

路由策略是影响网络模拟规模与性能的一个关键因素。MTree_Nix路由策略是目前网络模拟中综合性能较优的路由策略之一。分析了MTree_Nix路由策略在覆盖率计算以及路由信息预计算方面的缺陷,提出采用端到端的方式进行路由计算存储,并采用阈值与步数相结合的方法来稳定并提高最小生成树覆盖率。实验结果表明,改进后的MTree_Nix路由策略与改进之前相比,存储空间减少了约2%,路由预计算时间减少了约98%,模拟运行时间减少了约38%。

ZigBee网络中Cluster-Tree拓扑的改进与优化

无线传感器网络(WSN)是一种具有感测、计算和传输能力的小型传感器节点的集合。由于单个传感器节点的功能有限,特别是能量的存储和数据的存储,所以需要制定良好的网络拓扑结构和路由协议。文中重点研究基于IEEE 802.15.4标准的Zig Bee无线传感器网络,提出基于最小生成树(MST)的高效聚类拓扑结构MSCT,最终的目的在于以最小的成本构建一个网络拓扑结构。文中的拓扑结构还考虑了室内环境,提出了处理墙壁和障碍物导致的路径损耗和信号衰减的度量,并计算节点之间的链接的权重。最后,通过能量的损耗和网络的寿命来论证文中提出的MSCT拓扑结构比Cluster-Tree拓扑结构更具有优势性。

MEAN-VARIANCE MODEL BASED ON FILTERS OF MINIMUM SPANNING TREE

This study aims to reduce the statistical uncertainty of the correlation coefficient matrix in the mean-variance model of Markowitz. A filtering algorithm based on minimum spanning tree （MST） is proposed. Daily data of the 30 stocks of the Hang Seng Index （HSI） and Dow Jones Index （DJI） from 2004 to 2009 are selected as the base dataset. The proposed algorithm is compared with the Markowitz method in terms of risk, reliability, and effective size of the portfolio. Results show that （1） although the predicted risk of portfolio built with the MST is slightly higher than that of Markowitz, the realized risk of MST filtering algorithm is much smaller; and （2） the reliability and the effective size of filtering algorithm based on MST is apparently better than that of the Markowitz portfolio. Therefore, conclusion is that filtering algorithm based on MST improves the mean-variance model of Markowitz.

ON THE INVERSE MINIMUM SPANNING TREE PROBLEM WITH MINIMUM NUMBER OF PERTURBED EDGES

Let G=<V, E, L> be a network with the vertex set V, the edge set E and the length vector L, and let T* be a prior determined spanning tree of G. The inverse minimum spanning tree problem with minimum number of perturbed edges is to perturb the length vector L to L+ , such that T* is one of minimum spanning trees under the length vector L+ and the number of perturbed edges is minimum. This paper establishes a mathematical model for this problem and transforms it into a minimum vertex covering problem in a bipartite graph G0, a path-graph. Thus a strongly polynomial algorithm with time complexity O(mn2) can be designed by using Hungarian method.

Efficient Minimum Spanning Tree Algorithms on the Reconfigurable Mesh

The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.

Investigating the Disparities of China's Insurance Market Based on Minimum Spanning Tree from the Viewpoint of Geography and Enterprise

In this paper, we investigate the disparities of China’s insurance market from the viewpoint of geography and enterprise by using the monthly data from January 2006 to December 2015. We divide the whole insurance market into two parts, namely property insurance and personal insurance.By constructing and analyzing minimum spanning trees of insurance market, we obtain the results as follows:(i) The connections between provinces are much closer than those of firms, and there are regional links between neighboring provinces in the minimum spanning tree(MST); and(ii) the domestic funded firms and foreign funded firms form two explicit clusters in the MSTs of property and personal insurance market.