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

针对一类带约束的支撑树形图容量扩张问题(CEPAC)展开研究。首先,在不考虑长度权重约束条件的情况下,分别求出关于扩容费用C最小的支撑树形图TC、关于长度权重w最小的支撑树形图Tw,关于系数s(e)=aw(e)+bC(e)最小的支撑树形图Ts,通过分析3棵支撑树之间的关系,获得C(TC)≤C(Ts)≤C(Tw)且C(Ts)是CEPAC问题的一个更佳的上界或下界的结论,其次,提出一个改进的拉格朗日松弛算法求解CEPAC问题,最后,通过实例验证了算法的有效性。

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

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

在网络中寻找最小树形图的简易算法

研究网络中支撑树形图的性质 ,提出了在网络图中寻找最小树形图的简易算法 ,并对算法的复杂性进行了讨论 ,还给出应用该算法进行计算的一个实际算例。

分数Hamilton圈与分数树形图

定义有向图的分数有向Hamilton圈和分数支撑树形图 ,讨论分数Hamilton圈、分数旅行售货员问题和分数支撑树形图基于线性规划的等价定义及多项式时间算法 .

有向图的满装

本文应用 Edmonds 定理得到了某些有向图中以固定顶点为根的弧互不交的支撑树形图的极大个数.

AN INCREMENTAL UPDATING ALGORITHM FOR MINING ASSOCIATION RULES

In this letter, on the basis of Frequent Pattern(FP) tree, the support function to update FP-tree is introduced, then an Incremental FP (IFP) algorithm for mining association rules is proposed. IFP algorithm considers not only adding new data into the database but also reducing old data from the database. Furthermore, it can predigest five cases to three cases.The algorithm proposed in this letter can avoid generating lots of candidate items, and it is high efficient.

有向网络中强连通支撑子图扩容问题

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