Capacity Expansion Problem of Strongly Connected Spanning Subgraph with Constraints

Based on the congestion problem faced by flow transmission equipment in communication networks, in this paper, the capacity expansion problem of strongly connected spanning subgraph with constraints (CEPSCSSC) in directed networks is proposed. Firstly, NP-hardness is analyzed via Hamiltonian cycle problem. Secondly, a strongly connected spanning subgraph G’ is constructed by looking for an inverse spanning arborescence and a spanning arborescence with the same root vertex through using Chu-Liu-Edmonds algorithm, and then G’ is modified until the constraint conditions are satisfied by using the basic transformation of the spanning arborescence and the inverse spanning arborescence. so a heuristic algorithm, using the idea of arc exchange with the minimum weight increment, is designed to solve the CEPSCSSC problem. Finally, it is proved that the heuristic algorithm is correct and its time complexity is O (mnlogn).