动态有向超图中限制不交B-路算法设计

Design of Restricted Disjoint B-Path Algorithm in Dynamic Directed Hypergraph

摘要: 超图在现实生活中有很重要的应用价值，比如信息传递、货物运输、商品配送等问题都可以归约到超图中建立数学模型并设计优化算法。而网络环境是会随时间发生连续动态变化的，故本文主要研究动态超图中的连通性问题。同时，由于大规模网络中故障的发生是不可避免的，而且是极具破坏性的，所以，提高网络的生存性能，保证网络的容错性有很重要的研究价值。设计不交超路径是提高网络容错性的主要解决方案。由于超路中B-路有很好的结构性质和广泛的应用背景，因此，本文在时变超图网络中考虑满足时间限制的不交B-路构建问题。目前由于动态网络研究的复杂性，连续时间动态网络背景的处理方法大多是采用时间离散化转换为静态网络去求近似解，本文考虑当给定起始时刻时，在时间范围[0,Τ]内每条超弧的延迟函数为连续时间动态函数的情况下，针对不交B-路问题给出最优解的求解算法，并证明算法的正确性及运算复杂度。

Abstract: Hypergraph has very important application value in real life, for example, information transmission, goods transportation, commodity distribution and other problems can be reduced to hypergraph to establish mathematical model and design optimization algorithm. The network environment will change continuously and dynamically with time, so this paper mainly studies the connectivity problem in dynamic hypergraph. At the same time, the occurrence of faults in large-scale networks is inevitable and extremely destructive. Therefore, it has important research value to improve the survival performance of networks and ensure the fault tolerance of networks. Designing disjoint hyperpath is the main solution to improve network fault tolerance. Because the B-path in hyperpath has good structural properties and wide application background, we consider the construction of disjoint B-paths satisfying time constraints in time-varying hypergraph networks in this paper. At present, due to the complexity of dynamic network research, most of the processing methods of continuous time dynamic network background adopt time discretization to static network to obtain approximate solutions. However, in this paper, when the starting time is given, the delay function of each super-arc within the time range [0,Τ] is continuous time dynamic function, the algorithm for solving the optimal solution of the disjoint B-path problem is given. Finally, the correctness and computational complexity of the algorithm are proved.