杨子兰^1,2，朱娟萍²，李睿¹，杨宇²

1. 云南大学旅游文化学院信息学院, 丽江 674199; 2. 云南大学数学与统计学院, 昆明 650091

出版日期:2021-08-25发布日期:2021-11-23

Strongly Connected Spanning Subgraph Capacity Expansion Problemin Directed Networks

YANG Zilan^1,2 ，ZHU Juanping²， LI Rui¹ ，YANG Yu²

1. Department of Information, Tourism and Culture College of Yunnan University, Lijiang 674199;2. Dept. of Mathematics and Statistics, Yunnan University, Kunming 650091

Online:2021-08-25Published:2021-11-23







摘要
图/表
参考文献
相关文章
编辑推荐
-->Metrics
本文评论

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

()

No related articles found!

-->

PDF全文下载地址:

http://sysmath.com/jweb_xtkxysx/CN/article/downloadArticleFile.do?attachType=PDF&id=14294