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 packa...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.展开更多
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 ...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.展开更多
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 p...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.展开更多
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,i...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.展开更多
覆盖网能有效分离网络应用与底层网络基础设施,提升服务质量(quality of service,QoS)和用户体验(quality of users’experience,QoE)。设计了一种普适性较强的覆盖网拓扑构建算法——基于最小生成树(minimum spanning tree,MST)的拓扑...覆盖网能有效分离网络应用与底层网络基础设施,提升服务质量(quality of service,QoS)和用户体验(quality of users’experience,QoE)。设计了一种普适性较强的覆盖网拓扑构建算法——基于最小生成树(minimum spanning tree,MST)的拓扑感知度约束(minimum spanning tree-based topology-aware degree bound,MST-TADB)覆盖网构建算法。该方法感知网络拓扑,逐步生成MST,同时参考节点的转发和计算能力作为节点度约束收敛算法。由仿真结果可知,和同类算法相比,本文方法的故障恢复率、恢复路径跳数惩罚、服务节点平均节点度和时间复杂度综合权衡较好,并保证了所构建的覆盖网的自愈性。展开更多
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...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.展开更多
In this paper, we propose a novel clustering topology control algorithm named Minimum Spanning Tree (MST)-based Clustering Topology Control (MCTC) for Wireless Sensor Networks (WSNs), which uses a hybrid approach to a...In this paper, we propose a novel clustering topology control algorithm named Minimum Spanning Tree (MST)-based Clustering Topology Control (MCTC) for Wireless Sensor Networks (WSNs), which uses a hybrid approach to adjust sensor nodes' transmission power in two-tiered hi- erarchical WSNs. MCTC algorithm employs a one-hop Maximum Energy & Minimum Distance (MEMD) clustering algorithm to decide clustering status. Each cluster exchanges information between its own Cluster Members (CMs) locally and then deliveries information to the Cluster Head (CH). Moreover, CHs exchange information between CH and CH and afterwards transmits aggregated in- formation to the base station finally. The intra-cluster topology control scheme uses MST to decide CMs' transmission radius, similarly, the inter-cluster topology control scheme applies MST to decide CHs' transmission radius. Since the intra-cluster topology control is a full distributed approach and the inter-cluster topology control is a pure centralized approach performed by the base station, therefore, MCTC algorithm belongs to one kind of hybrid clustering topology control algorithms and can obtain scalability topology and strong connectivity guarantees simultaneously. As a result, the network topology will be reduced by MCTC algorithm so that network energy efficiency will be improved. The simulation results verify that MCTC outperforms traditional topology control schemes such as LMST, DRNG and MEMD at the aspects of average node's degree, average node's power radius and network lifetime, respectively.展开更多
This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-...This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.展开更多
文摘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.
文摘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.
基金supported by the National Natural Science Foundation of China(Nos.61962034,61862058)Longyuan Youth Innovation and Entrepreneurship Talent(Individual)Project and Tianyou Youth Talent Lift Program of Lanzhou Jiaotong Univesity。
文摘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.
基金National Natural Science Foundation of China(No.61761027)。
文摘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.
基金supported by the funds project under the Ministry of Education of the PRC for young people who are devoted to the researches of humanities and social sciences under Grant No. 09YJC790025
文摘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.
文摘In this paper, we propose a novel clustering topology control algorithm named Minimum Spanning Tree (MST)-based Clustering Topology Control (MCTC) for Wireless Sensor Networks (WSNs), which uses a hybrid approach to adjust sensor nodes' transmission power in two-tiered hi- erarchical WSNs. MCTC algorithm employs a one-hop Maximum Energy & Minimum Distance (MEMD) clustering algorithm to decide clustering status. Each cluster exchanges information between its own Cluster Members (CMs) locally and then deliveries information to the Cluster Head (CH). Moreover, CHs exchange information between CH and CH and afterwards transmits aggregated in- formation to the base station finally. The intra-cluster topology control scheme uses MST to decide CMs' transmission radius, similarly, the inter-cluster topology control scheme applies MST to decide CHs' transmission radius. Since the intra-cluster topology control is a full distributed approach and the inter-cluster topology control is a pure centralized approach performed by the base station, therefore, MCTC algorithm belongs to one kind of hybrid clustering topology control algorithms and can obtain scalability topology and strong connectivity guarantees simultaneously. As a result, the network topology will be reduced by MCTC algorithm so that network energy efficiency will be improved. The simulation results verify that MCTC outperforms traditional topology control schemes such as LMST, DRNG and MEMD at the aspects of average node's degree, average node's power radius and network lifetime, respectively.
基金the National Natural Science Foundation of China under Grant Nos.10401038,60373012 and 70221001the Key Project of Chinese Ministry of Education under Grant No.106008
文摘This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.
