山西大学学报（自然科学版）2024，Vol.47Issue(1)：112-121,10.DOI:10.13451/j.sxu.ns.2023026
时间约束下最优时变后向超路近似算法设计
Approximate Algorithm Design of Optimal Time-varying Backward Hyperpaths with Time Constraints
摘要
Abstract
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.关键词
时变后向超图/时间约束下的最优超路/近似算法/伪多项式时间算法/时间离散Key words
time-varying backward hypergraph/optimal hyperpath with time constraints/approximate algorithm/pseudopolynomial time algorithm/time discretization分类
数理科学引用本文复制引用
邢治乐,张淑蓉..时间约束下最优时变后向超路近似算法设计[J].山西大学学报（自然科学版）,2024,47(1):112-121,10.基金项目
山西省自然科学基金(202103021224058) （202103021224058）
