带约束的支撑树形图容量扩张问题  

Capacity Expansion Problem of Spanning Arborescence with Constraints

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

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

出　　处：《工程数学学报》2022年第5期739-749,共11页Chinese Journal of Engineering Mathematics

基　　金：云南省教育厅科学研究基金(2016ZDX152,2017ZDX270,2022J1217)。

摘　　要：将通信网络扩张升级问题抽象为带约束的支撑树形图容量扩张问题(CEPAC),并针对该问题进行研究。首先,由0-1背包问题归约出CEPAC问题的实例,进而分析CEPAC问题的NP-困难性。其次,采用支撑树Megiddo参数搜索和拟阵交的Megiddo参数搜索策略,建立支撑树形图多面体与拟阵交之间的关系,将一棵最优支撑树形图通过基本变换转换成与之相邻的最优支撑树形图,为CEPAC问题设计一个(2,1)-近似的带约束的拟阵交算法。最后,考虑最小支撑树形图容量扩张问题(CEPMA),并利用字典序方法对朱–刘算法进行改进求解CEPMA问题。We consider the problem of communication network expansion and upgrading,which is abstracted as the capacity expansion problem of spanning arborescence with constraints(CEPAC)in directed networks.Firstly,we prove that CEPAC problem is NP-hard by constructing an instance of CEPAC based on 0-1 knapsack problem.Secondly,by Megiddo parameter search of the spanning tree and Megiddo parameter search strategy of matroid intersection,we establish the relationship between the spanning arborescence polytope and the matroid intersection,and transform an optimal spanning arborescence into an adjacent optimal spanning arborescence through the basic transformation.Then,we design a(2,1)-approximate matroid intersection algorithm with constraints for CEPAC problem.Finally,we discuss the capacity expansion problem minimum arborescence(CEPMA)and solve it by modifying ChuLiu-Edmonds algorithm with lexicographical order.

关 键 词：支撑树形图 拟阵交 相邻关系 字典序 

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