中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 2: 151 - 158

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.02.012

The expansion problem of maximum capacity spanning arborescence in networks

Expand
  • 1. Department of Information, Lijiang Culture and Tourism College, Lijiang 674199, Yunnan, China
    2. School of Mathematics and Statistics, Yunnan University, Kunming 650091, Yunnan, China

Received date: 2021-03-26

  Online published: 2024-06-07

Copyright

, 2024, All rights reserved, without authorization
Fold

Abstract

For the expansion problem of the maximum capacity spanning arborescence in networks (EMCSA), NP-hardness is proved by constructing an instance of EMCSA from 0-1 knapsack problem, and a heuristic algorithm is designed. Finally, one special version of EMCSA, the expansion problem of the minimum arc number on the maximum capacity spanning arborescence in networks (NEMCSA), is considered. For NEMCSA, a strongly polynomial algorithm, in $O(mn) $ time, is provided by substituting the arc with the minimum weight difference.

Key words： maximum capacity arborescence; capacity expansion; NP-hard; heuristic algorithm; polynomial time algorithm

Cite this article

Zilan YANG, Juanping ZHU, Yu YANG . The expansion problem of maximum capacity spanning arborescence in networks[J]. Operations Research Transactions, 2024 , 28(2) : 151 -158 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.02.012

References

1 黄韬,霍如,刘江,等.未来网络发展趋势与展望[J].中国科学: 信息科学,2019,49,941-948.
2 张超. 有向网络容量扩张问题研究[D]. 武汉: 华中科技大学, 2007.
3 LiJ P,ZhuJ P.The capacity expansion path problem in networks[J].Journal of Applied Mathematics,2013,7(16):361-376.
4 杨宇. 有向网络中最大容量树形图扩容问题[D]. 昆明: 云南大学, 2011.
5 朱娟萍. 限制性网络扩容问题[D]. 昆明: 云南大学, 2011.
6 李彬,张洁,陈宋宋,等.基于复杂网络的电力通信网扩容保护策略[J].电网技术,2018,42(6):1974-1980.
7 王凌风,卢国潇.基于帕累托法则的网络负荷扩容研究[J].邮电设计技术,2019,7,54-59.
8 FragkosL,CordeauJ F,JansR.Decomposition methods for large-scale network expansion problems[J].Transportation Research Part B,2021,144,60-80.
9 张国清,程苏琦.小世界网络中的删边扩容效应[J].中国科学: 信息科学,2012,42(2):151-160.
10 赵焱鑫,李黎,王小明.复杂网络加边扩容策略研究[J].计算机应用研究,2015,32(6):1839-1841.
11 FulkersonD R.Increasing the capacity of a network: The parametric budget problem[J].Management Science,1959,5(4):472-483.
12 SchwarzS,KrumkeS O.On budget—constrained flow improvement[J].Information Proccssing Letters,1998,66,291-297.
13 YangC,LiuJ L.A capacity expansion problem with budget constraint and bottleneck limitation[J].Acta Mathematica Scientia,2002,22(2):207-212.
14 ZhangJ Z,YangC,LinY X.A class of bottleneck expansion problems[J].Computers & Operations Research,2001,28(6):505-519.
15 ZhangJ Z,LiuJ L.An oracle strongly polynomial algorithm for bottleneck expansion problems[J].Operation Methods and Software,2002,17(1):61-75.
16 YangC,ZhangJ Z.On the bottleneck capacity expansion problems on networks[J].Acta Mathematica Scientia,2006,26B(2):202-208.
17 TaghaviM,HuangK.A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints[J].Annals of Operations Research,2020,284,605-621.
18 田丰,马仲蕃.图与网络流理论[M].北京:科学出版社,1987.
19 ChuY J,LiuT H.On the shortest arborescence of a directed graph[J].Science Sinica,1965,14,1396-1400.
20 EdmondsJ.Optimum branchings[J].Research of the National Bureau of Standards,1967,71B,233-240.
Options
Outlines

/

〈 〉