The expansion problem of maximum capacity spanning arborescence in networks.

For the expansion problem of the maximum capacity spanning arborescence in networks (EMCSA), NP-hardness is proved by constructing an instance of EMCSA 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. [ABSTRACT FROM AUTHOR]