限制性路由与网络构建问题 12月12日
【摘要】中国邮递员问题是一种非常重要的路由问题,本文研究了中国邮递员问题的推广形式,即混合图中限制性路由问题,并研究了无向图中限制性边路由问题和有向图中限制性弧路由问题,分别设计了求解它们的一个近似算法和两个多项式时间最优算法;研究了满足γ-三角不等式性质的最大权重哈密尔顿路问题,设计了两个随机算法和一个近似算法对其进行求解;研究了两类网络构建问题,即限制性最短路网络构建问题和具有最小比值的网络构 […]
【摘要】中国邮递员问题是一种非常重要的路由问题,本文研究了中国邮递员问题的推广形式,即混合图中限制性路由问题,并研究了无向图中限制性边路由问题和有向图中限制性弧路由问题,分别设计了求解它们的一个近似算法和两个多项式时间最优算法;研究了满足γ-三角不等式性质的最大权重哈密尔顿路问题,设计了两个随机算法和一个近似算法对其进行求解;研究了两类网络构建问题,即限制性最短路网络构建问题和具有最小比值的网络构 […]