典型文献
带约束的支撑树形图容量扩张问题
文献摘要：
将通信网络扩张升级问题抽象为带约束的支撑树形图容量扩张问题(CEPAC),并针对该问题进行研究.首先,由0-1背包问题归约出CEPAC问题的实例,进而分析CEPAC问题的NP-困难性.其次,采用支撑树Megiddo参数搜索和拟阵交的Megiddo参数搜索策略,建立支撑树形图多面体与拟阵交之间的关系,将一棵最优支撑树形图通过基本变换转换成与之相邻的最优支撑树形图,为CEPAC问题设计一个(2,1)-近似的带约束的拟阵交算法.最后,考虑最小支撑树形图容量扩张问题(CEPMA),并利用字典序方法对朱–刘算法进行改进求解CEPMA问题.
文献关键词：
支撑树形图;拟阵交;相邻关系;字典序
中图分类号：
作者姓名：
杨子兰;朱娟萍;李睿
作者机构：
丽江文化旅游学院信息学院,丽江 674199;云南大学数学与统计学院,昆明 650091
文献出处：
引用格式：
[1]杨子兰;朱娟萍;李睿-.带约束的支撑树形图容量扩张问题)[J].工程数学学报,2022(05):739-749
A类：
支撑树形图,CEPAC,问题归约,Megiddo,拟阵交,最小支撑树,CEPMA
B类：
通信网络,背包问题,NP,困难性,搜索策略,多面体,一棵,转换成,问题设计,用字,字典序,相邻关系
AB值：
0.130504
相似文献
机标中图分类号，由域田数据科技根据网络公开资料自动分析生成，仅供学习研究参考。
