在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2022, Vol. 39 ›› Issue (5): 739-749.doi: 10.3969/j.issn.1005-3085.2022.05.005

• • 上一篇    下一篇

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

杨子兰1,2,  朱娟萍2,    李  睿2   

  1. 1. 丽江文化旅游学院信息学院，丽江  674199; 2. 云南大学数学与统计学院，昆明  650091
  • 出版日期:2022-10-15 发布日期:2022-12-15
  • 通讯作者: 朱娟萍 E-mail: jpzhu@ynu.edu.cn
  • 基金资助:
    云南省教育厅科学研究基金(2016ZDX152; 2017ZDX270; 2022J1217).

Capacity Expansion Problem of Spanning Arborescence with Constraints

YANG Zilan1,2,   ZHU Juanping2,    LI Rui2   

  1. 1. Department of Information,  Lijiang Culture and Tourism College, Lijiang 674199;
    2. School of Mathematics and Statistics, Yunnan University, Kunming 650091
  • Online:2022-10-15 Published:2022-12-15
  • Contact: J. Zhu. E-mail address: jpzhu@ynu.edu.cn
  • Supported by:
    The Scientific Research Foundation of Yunnan Education Department (2016ZDX152; 2017ZDX270; 2022J1217).

PDF (PC)

54

摘要：

将通信网络扩张升级问题抽象为带约束的支撑树形图容量扩张问题(CEPAC)，并针对该问题进行研究。首先，由0-1背包问题归约出CEPAC问题的实例，进而分析CEPAC问题的NP-困难性。其次，采用支撑树Megiddo参数搜索和拟阵交的Megiddo参数搜索策略，建立支撑树形图多面体与拟阵交之间的关系，将一棵最优支撑树形图通过基本变换转换成与之相邻的最优支撑树形图，为CEPAC问题设计一个$(2,1)$-近似的带约束的拟阵交算法。最后，考虑最小支撑树形图容量扩张问题(CEPMA)，并利用字典序方法对朱–刘算法进行改进求解CEPMA问题。

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

Abstract:

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 Chu-Liu-Edmonds algorithm with lexicographical order.

Key words: spanning arborescence, matroid intersection, adjacency, lexicographical order

中图分类号: