论文部分内容阅读
路由是在网络中选择运送物品的路径的过程,它在各种网络中都有应用。在本文中,我们主要讨论了无线通讯网络和交通运输网络中与路由相关的两个组合优化问题,即最少最短路中间节点并集问题和带容量限制的车辆路由问题。我们证明了这两个问题都是NP-难的,设计了求解第一个问题的一个最好可能的近似算法,并设计了求解第二个问题的一个5-近似算法。