有向网络中强连通支撑子图扩容问题

Strongly Connected Spanning Subgraph Capacity Expansion Problem in Directed Networks

针对有向网络中的强连通支撑子图弧扩容问题,提出了 GSCSCE模型.首先研究不受限制的两种特殊情况:最少弧强连通支撑子图扩容问题(MNSCSCE)和最小费用强连通支撑子图扩容问题(MCSCSCE),并把它们的模型转化为赋权形式的强连通支撑子图问题,分别给出了 2-近似算法,时间复杂性均为O(mn).最后讨论受限制问题的特殊情况:最少弧受限强连通支撑子图扩容问题(NCSCSS),用支撑树形图的简单变换给出了一个2-近似算法,时间复杂性为O(mn).

The model of general strongly connected spanning subgraph capacity expansion(GSCSCE) is proposed.Firstly,two special versions without weight constraints are discussed:The minimum number strongly connected spanning subgraph capacity expansion problem(MNSCSCE) and the minimum cost strongly connected spanning subgraph expansion problem(MCSCSCE).For each problem,a 2-approxima-tion algorithm,in O(mn) time,is designed respectively by converting the model to a weighted minimum strongly connected spanning subgraph problem.Finally,the minimum number constrained strongly connected spanning subgraph capacity expansion problem(NCSCSS),the special version with weight constraints,is considered.This problem is solved approximately with factor 2,in O(mn) time,by the technology of arborescence exchanges.