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

Strongly Connected Spanning Subgraph Capacity Expansion Problem in Directed Networks

作　　者：杨子兰[1,2] 朱娟萍 李睿[1] 杨宇 YANG Zilan;ZHU Juanping;LI Rui;YANG Yu(Department of Information,Tourism and Culture College of Yunnan University,Lijiang 674199;Dept,of Mathematics and Statistics,Yunnan University,Kunming 650091)

机构地区：[1]云南大学旅游文化学院信息学院,丽江674199 [2]云南大学数学与统计学院,昆明650091

出　　处：《系统科学与数学》2021年第8期2170-2181,共12页Journal of Systems Science and Mathematical Sciences

基　　金：国家自然科学基金项目(11126355);云南省教育厅科学研究基金项目(2016ZDX152,2017ZDX270,2019J0235)资助课题。

摘　　要：针对有向网络中的强连通支撑子图弧扩容问题,提出了 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.

关 键 词：容量扩容 支撑子图 强连通子图 逆支撑树形图 近似算法 

分 类 号：O157.5[理学—数学]