限制性路构建问题

发布时间：2020-07-11 06:45

【摘要】：本论文主要研究限制性路构建问题,包括两个基本内容,即限制性路增广问题和限制性路构建问题。限制性路增广问题可以描述为:给定一个有向图D =(V,A;c)以及图D中的一条s-t有向路Ps,t,其中s,t∈V,费用函数c:A →R+,要寻找弧子集A1(?)A-A(Ps,t),满足对任一条弧a ∈ A(Ps,t)(或者对任一个顶点u ∈ V(Ps,t)-{s,t}),在诱导子图Ps,t ∪A1-{a}(或者诱导子图Ps,t ∪A1-{u})中仍存在一条s-t有向路,目标是使得所选弧集合A1的总费用c(A1)达到最小,即c(A1)=∑e∈A1c(e)达到最小。对于这两个问题,本文设计了两个时间复杂度为O(mn)多项式时间最优算法,其中m表示有向图D中弧的数目,n表示有向图D中顶点的数目。在上述问题的基础上,本文研究了限制性路构建问题,具体描述为:给定一个赋权有向图D=(V,A;w,c),长度为L的材料若干,以及图DD中一条s-t有向路Ps,t,其中s,t∈V,长度函数w:A→RR+,施工费用函数c:→→R+,要构建一个弧集合A1(?)A-A(Ps,t),满足对任一条弧a∈A(Ps,t(或者对任一个顶点u∈V(s,t)-{s,t}),在诱导子图Ps,u A1—{a}(或者诱导子图Ps,∪ A1—{u})中仍存在一条s-t有向路,目标是使得构建弧集合A1的总费用cost(A1)达到最小,即cost(A1)= ∑e∈A1(e)+k(A1)·c0达到最小,这里总费用包括施工费用和购买材料的费用,k(A1)表示构建弧集合A1所需材料的根数,c0为每根材料的购买费用。对于此类问题,本文设计了两个时间复杂度为O(mn)的2-近似算法,其中m表示有向图D中弧的数目,n表示有向图D中顶点的数目。
【学位授予单位】：云南大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【参考文献】