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

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