The expansion problem of maximum capacity spanning arborescence in networks
For the expansion problem of the maximum capacity spanning arbores-cence in networks(EMCSA),NP-hardness is proved by constructing an instance of EM-CSA from 0-1 knapsack problem,and a heuristic algorithm is designed.Finally,one special version of EMCSA,the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks(NEMCSA),is considered.For NEMCSA,a strongly polynomial algorithm,in O(mn)time,is provided by substituting the arc with the minimum weight difference.
maximum capacity arborescencecapacity expansionNP-hardheuristic algorithmpolynomial time algorithm
万方数据
维普
