Approximate Algorithm Design of Optimal Time-varying Backward Hyperpaths with Time Constraints
Time-varying shortest path design is an important problem in network optimization.Especially for networks with complex structures,time-varying hypergraph is usually used as the network topology,so the research of path optimization in time-varying hy-pergraph has received wide attention.Time-varying backward hypergraph(TVBH)is a special kind of time-varying hypergraph.In this paper,we mainly studies the problem of constructing the optimal time-varying backward hyperpath(TV-B hyperpath)between a given source node and all network nodes satisfying time constraints in TVBH.Because this kind of problem is NP(Non-determinis-tic Polynomial)complete,we design a pseudopolynomial time algorithm using the method of time discretization,and further pro-pose an effective approximation algorithm to obtain the(1+ε)approximate solution.Finally,an example simulation shows that us-ing the approximation algorithm can significantly reduce the computational complexity.
time-varying backward hypergraphoptimal hyperpath with time constraintsapproximate algorithmpseudopolynomial time algorithmtime discretization
国家科技期刊平台
NSTL
万方数据
