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...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)).展开更多
针对卫星网络动态环境下的高速信息传输、业务类型差异大等特点,提出一种综合考虑各业务QoS(Quality of Service)指标的可靠性分析方法。在卫星通信网络实际运行周期内,通信系统往往处于逐渐劣化过程中,导致卫星的节点和链路除正常工作...针对卫星网络动态环境下的高速信息传输、业务类型差异大等特点,提出一种综合考虑各业务QoS(Quality of Service)指标的可靠性分析方法。在卫星通信网络实际运行周期内,通信系统往往处于逐渐劣化过程中,导致卫星的节点和链路除正常工作和完全失效外,还存在部分失效的工作状态。本文在链路多状态基础上基于最小路集算法(Minimum Path Set Algorithms,MPSA)在不同业务的QoS指标(时延、带宽和丢包率)约束下,得出满足该业务QoS约束的所有可靠路径集,对路径集中路径进行不交化处理得到网络端-端可靠性。研究结果表明,不同业务由于QoS需求的差异导致网络端-端可靠性不同,所提算法与传统算法相比更加符合实际。由于实际卫星网络环境中会采用端-端并行多路径传输(Multi-Path Transmission,MTP),本文在上述研究的基础上,进一步对多路径的端-端可靠性进行了研究,结果表明多路径数据传输可靠性高。展开更多
The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving th...The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.展开更多
文摘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)).
文摘针对卫星网络动态环境下的高速信息传输、业务类型差异大等特点,提出一种综合考虑各业务QoS(Quality of Service)指标的可靠性分析方法。在卫星通信网络实际运行周期内,通信系统往往处于逐渐劣化过程中,导致卫星的节点和链路除正常工作和完全失效外,还存在部分失效的工作状态。本文在链路多状态基础上基于最小路集算法(Minimum Path Set Algorithms,MPSA)在不同业务的QoS指标(时延、带宽和丢包率)约束下,得出满足该业务QoS约束的所有可靠路径集,对路径集中路径进行不交化处理得到网络端-端可靠性。研究结果表明,不同业务由于QoS需求的差异导致网络端-端可靠性不同,所提算法与传统算法相比更加符合实际。由于实际卫星网络环境中会采用端-端并行多路径传输(Multi-Path Transmission,MTP),本文在上述研究的基础上,进一步对多路径的端-端可靠性进行了研究,结果表明多路径数据传输可靠性高。
基金supported by the National Natural Science Foundation of China(Grant Nos.61806050,61972063,61976050)the Fundamental Research Funds for the Central Universities(2412020FZ030,2412019ZD013,2412019FZ051)Jilin Science and Technology Association(QT202005).
文摘The minimum independent dominance set(MIDS)problem is an important version of the dominating set with some other applications.In this work,we present an improved master-apprentice evolutionary algorithm for solving the MIDS problem based on a path-breaking strategy called MAE-PB.The proposed MAE-PB algorithm combines a construction function for the initial solution generation and candidate solution restarting.It is a multiple neighborhood-based local search algorithm that improves the quality of the solution using a path-breaking strategy for solution recombination based on master and apprentice solutions and a perturbation strategy for disturbing the solution when the algorithm cannot improve the solution quality within a certain number of steps.We show the competitiveness of the MAE-PB algorithm by presenting the computational results on classical benchmarks from the literature and a suite of massive graphs from real-world applications.The results show that the MAE-PB algorithm achieves high performance.In particular,for the classical benchmarks,the MAE-PB algorithm obtains the best-known results for seven instances,whereas for several massive graphs,it improves the best-known results for 62 instances.We investigate the proposed key ingredients to determine their impact on the performance of the proposed algorithm.
