无圈反向超图中Min-Max不相交反向超路算法设计

超图与反向超图是计算机网络和通信网络采用的一类重要的网络拓扑结构,为提高网络以及传输路径容错性,不相交路径设计与优化成为重要的研究课题。本文在有向无圈的反向超图中,当每一条反向超弧的尾节点数不超过给定常数λ时,对构建源点与汇点间两条点不相交反向超路(B超路)的Min-Max优化问题进行研究,使得两条反向超路中权值较大者的值能够达到全局最小。为解决该问题,首先构造并设计了基于原图的辅助图,该辅助图也是有向无圈的反向超图,并将原问题转化为辅助图的多权值函数B超路优化问题。从而设计了伪多项式算法得到该问题的最优解。基于该算法,进一步给出了近似算法的设计方案得到(1+ε)近似解,从而有效降低了计算复杂性。