一类新型网络构建问题的算法设计与分析
刘丽, 张安, 陈永, 陈光亭
研究了一类新型网络构建问题,使有向网络中子网络的弧在切割成权值为L的分段时所产生的总分段数尽可能小。针对问题,假设有向网络每条弧的权值不小于L,给出子网络结构为有向路或强连通支撑子网络两种情形时的近似算法,并证明算法的最坏情况界分别为3/2和3。
:杭州电子科技大学学报(自然科学版)