Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (2): 169-171.

• 网络、通信与安全 • Previous Articles     Next Articles

Optimization of link disjoint path algorithm

ZHANG Guang-yue1,WANG Ze-yan2,ZHANG Shen-ru2   

  1. 1.Institute of Communications Engineering,PLA University of Science and Technology,Nanjing 210007,China
    2.Institute of Sciences,PLA University of Science and Technology,Nanjing 210007,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-11 Published:2008-01-11
  • Contact: ZHANG Guang-yue

一种链路分离路径算法的优化

张广跃1,汪泽焱2,张申如2   

  1. 1.解放军理工大学 通信工程学院 研究生二队,南京 210007
    2.解放军理工大学 理学院,南京 210007
  • 通讯作者: 张广跃

Abstract: Algorithm DIMCRA can solve link disjoint paths problem with multiple additive constraints well.This article has analyzed algorithm DIMCRA,and has proved that the there is a sort of the link-disjoint problem the algorithm DIMCRA cannot solved.Then author has introduced the combination difference which has optimized the old algorithm,and has given an instance to show that the improved algorithm can improve the algorithm’s performance.

Key words: multiple constraints, link disjoint, DIMCRA-improved

摘要: DIMCRA算法能很好地解决多个加性约束下的链路分离路径问题的算法。论文对DIMCRA算法进行了理论分析,并证明了存在一类链路分离路径问题是该算法不能解决的。随后在算法中引入了组合差分的概念,对算法进行了优化,并通过实例仿真说明了改进后的算法能弥补原算法的不足。

关键词: 多约束, 链路分离, DIMCRA改进