来源：期刊VIP网 时间：
作者：邢治乐;张淑蓉;
单位：太原理工大学数学学院;
摘要：时变最短路径设计是网络优化的一类重要问题。特别是针对结构复杂的网络，通常采用时变超图作为网络拓扑结构，所以在时变超图中研究路径优化问题受到广泛关注。时变后向超图（TVBH）是一类特殊的时变超图。文章主要是研究了在TVBH中构建满足时间约束的给定源点与所有网络节点间的最优时变后向超路（TV-B超路）问题。由于该类问题是NP(Non-deterministic Polynomial)完全的，文章利用时间离散的方法设计了伪多项式时间算法，并进一步提出了有效近似算法得到了(1+ε)近似解。最后通过实例仿真表明了利用近似算法能够显著降低运算复杂性。
关键词：时变后向超图;;时间约束下的最优超路;;近似算法;;伪多项式时间算法;;时间离散
基金资助：山西省自然科学基金（202103021224058）
