%0 Journal Article
%T 多约束最短链路分离路径精确算法
%A 熊轲？
%A 裘正定？
%A 郭宇春？
%A 张宏科？
%A 秦雅娟？
%J 软件学报
%P 1744-1757
%D 2010
%X 在通信的源和目的间寻找两条(主用和备用)链路分离的qos路径是提供可靠qos路由的重要途径.现有求解多约束链路分离路径对(multi-constrainedlink-disjointpathpair,简称mclpp)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了mclpp问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解mclpp问题的精确算法(link-disjointoptimalmulti-constrainedpathsalgorithm,简称lidompa算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了lidompa的搜索空间.大量的实验结果表明,lidompa的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.
%K 服务质量路由
%K 网络可靠性
%K 链路分离路径
%K 多约束路由
%K 最优解
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=3589&flag=1