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.

基于Spanning Tree的网络负载均衡实现研究

冗余的网络环境能够保证网络的稳定运行,生成树协议能够防止冗余的网络环境下产生的网络环路,生成树的默认配置导致整个网络运行效率低下,与VLAN配合可以提供链路负载均衡,实现网络的安全、稳定、高效运行.本文通过网络拓扑的构建以及具体的配置过程实现了基于生成树的网络负载均衡.

A NEW ALGORITHM FOR ALL EFFICIENT SPANNING TREES

Ｃｏｒｌｅｙ提出了一种求所有有效生成树的算法，但该算法得到的最终解含有许多非有效的生成树。本文提出一种新的算法，首先指明了Ｃｏｒｌｅｙ算法理论基础的缺陷，然后进一步提出并证明了一个子树是有效生成树的子树的两个必要条件。根据这个结果，建立了这种新算法并证明了它的有效性。

An Explicit Integer Programming Model of the Minimal Spanning Tree Problem for Digraphs with Asymmetric Weights

As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packages such as LINDO, and furthermore this model is extendedinto the stochastic version, that is, the minimal spanning tree problem for the digraph with theweights is not constant but random variables. Several algorithms are also developed to solve themodels. Finally, a numerical demonstration is given.

A Table Based Algorithm for MinimumDirected Spanning Trees

As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.

Table Operation Method for Optimal Spanning Tree Problem

As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.

Spanning tree-based algorithm for hydraulic simulation of large-scale water supply networks

With the purpose of making calculation more efficient in practical hydraulic simulations, an improved algorithm was proposed and was applied in the practical water distribution field. This methodology was developed by expanding the traditional loop-equation theory through utilization of the advantages of the graph theory in efficiency. The utilization of the spanning tree technique from graph theory makes the proposed algorithm efficient in calculation and simple to use for computer coding. The algorithms for topological generation and practical implementations are presented in detail in this paper. Through the application to a practical urban system, the consumption of the CPU time and computation memory were decreased while the accuracy was greatly enhanced compared with the present existing methods.

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.

The minimal spanning tree method for calculating seismic multi-fractal

There are many methods to calculate seismic fractal at present. However, there are still more or less questions to every method. In this paper, we introduce a new way to calculate seismic fractal-the minimal spanning tree. We make an important improvement for this method. By studying some seismic events of four regions including Wushi, Wusu, Tangshan and Haicheng, we obtain that before the strong earthquake occurrence, the multi-fractal spectrum of the space-time distribution of earthquakes changes from centralized to loose. The result shows that the complexity of fractal structure and the inhomogeneity of the space-time distribution of earthquakes are both increasing. By studying the numerical simulation of point sets, we draw the conclusion that the physical essence of multi-fractal spectrums before and after a strong earthquake occurrence is a changing process from homogeneous to inhomogeneous, from simple to complex.

AEESPAN: Automata Based Energy Efficient Spanning Tree for Data Aggregation in Wireless Sensor Networks

In Wireless Sensor Networks (WSNs), sensor nodes are developed densely. They have limit processing ca-pability and low power resources. Thus, energy is one of most important constraints in these networks. In some applications of sensor networks, sensor nodes sense data from the environment periodically and trans-mit these data to sink node. In order to decrease energy consumption and so, increase network’s lifetime, volume of transmitted data should be decreased. A solution, which is suggested, is aggregation. In aggrega-tion mechanisms, the nodes aggregate received data and send aggregated result instead of raw data to sink, so, the volume of the transmitted data is decreased. Aggregation algorithms should construct aggregation tree and transmit data to sink based on this tree. In this paper, we propose an automaton based algorithm to con-struct aggregation tree by using energy and distance parameters. Automaton is a decision-making machine that is able-to-learn. Since network’s topology is dynamic, algorithm should construct aggregation tree peri-odically. In order to aware nodes of topology and so, select optimal path, routing packets must be flooded in entire network that led to high energy consumption. By using automaton machine which is in interaction with environment, we solve this problem based on automat learning. By using this strategy, aggregation tree is reconstructed locally, that result in decreasing energy consumption. Simulation results show that the pro-posed algorithm has better performance in terms of energy efficiency which increase the network lifetime and support better coverage.

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.

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.

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)).

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.

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.

Closure for Spanning Trees with <i>k</i>-Ended Stems

Let T be a tree. The set of leaves of Τ is denoted by Leaf(Τ). The subtree Τ—Leaf(Τ) of T is called the stem of Τ. A stem is called a k-ended stem if it has at most k-leaves in it. In this paper, we prove the following theorem. Let G be a connected graph and k≥2 be an integer. Let u and ν be a pair of nonadjacent vertices in G. Suppose that |NG(u)∪NG(v)|≥|G|-k-1. Then G has a spanning tree with k-ended stem if and only if G+uv has a spanning tree with k-ended stem. Moreover, the condition on |NG(u)∪NG(v)| is sharp.

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 Kemeny’s Constant and Spanning Trees of Hexagonal Ring Network

Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology of hepatitis C virus(HCV)infection.On the other hand,Kemeny’s constant(Ω)is a beneficial quantifier characterizing the universal average activities of a Markov chain.This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si.Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues.Motivated by Levene and Loizou,we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial.Based on the achieved results,entirely results are obtained for the M鯾ius hexagonal ring network.

Packet Compression Ratio Dependent Spanning Tree for Convergecast

A convergecast is a popular routing in sensor networks. It periodically forwards collected data at every sensor node along a configured routing path to the outside of a sensor network via the base station (BS). To extend the lifetime of energy-limited sensor networks, many previous researches proposed schemes for data compression. However, few researches investigated the relation between packet compression ratio and spanning trees. We propose packet Compression ratio dependent Spanning Tree (CST) which can provide effective routing paths in terms of the tree length for all ranges of compression ratio f. CST is equivalent to the Shortest Path spanning Tree (SPT) which is optimum in the case of no-compression (f = 0) and is equivalent to the Minimum Spanning Tree (MST) in the case of full-compression (f = 1). CST outperforms SPT and MST for any range of f (0 &amp;lt;f &amp;lt;1). Through simulation we show CST provides shorter paths than MST and SPT in terms of the tree length by 34.1% and 7.8% respectively. We confirm CST is very useful in convergecasts.

Minimum Diameter Spanning Tree

In this paper, we discuss the simple connected graphs which have a minimum diameter spanning tree such that both have same domination number.