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

Design of Min-Max Disjoint Backward Hy-perpaths Algorithm in Acyclic Backward Hypergraph

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

Abstract: Hypergraph and backward hypergraph are an important class of the network topology used in computer networks and communication networks. In order to improve the fault tolerance of net-works and transmission paths, the design and optimization of disjoint paths have become im-portant research topics. In this paper, in the directional acyclic backward hypergraph, when the tail node number of each backward hyperarc does not exceed the given constant λ , the Min-Max opti-mization problem of constructing two node-disjoint backward hyperpaths (B-hyperpaths) from the source node to the sink node is researched, so that the value of the greater weight in this two node-disjoint backward hyperpaths can reach the global minimum. In order to solve this problem, the auxiliary hypergraph based on the original hypergraph is constructed and designed firstly, which is also a directional acyclic backward hypergraph. The original problem is transformed into a B-hyperpath optimization problem with multi-weight function in the auxiliary hypergraph. Thus a pseudo-polynomial algorithm is designed to obtain an optimal solution to the problem. Based on this algorithm, the design scheme of the approximation algorithm is further given to obtain an (1+ε) approximate solution which effectively reduce the complexity of calculation.