科研之友
微信
新浪微博
Facebook
分享链接
摘要
时变最短路径设计是网络优化的一类重要问题。特别是针对结构复杂的网络，通常采用时变超图作为网络拓扑结构，所以在时变超图中研究路径优化问题收到广泛关注。时变后向超图（TVBH）是一类特殊的时变超图。文章主要是研究了在TVBH中构建满足时间约束的给定源点与所有网络节点间的最优时变后向超路（TV-B超路）问题。由于该类问题是NP完全的，文章利用时间离散的方法设计了伪多项式时间算法，并进一步提出了有效近似算法得到了(1+ε)近似解。最后通过实例仿真表明了利用近似算法能够显著降低运算复杂性。
-
单位数学学院; 太原理工大学
