论文部分内容阅读
树上1-点中心选址逆问题是指对于已知的一棵无向树以及关于它的一些参数(主要是每条边的原边长、边长上限和下限及每条边增加和减少单位长度分别所需的费用),在最小的总花费下通过修改树中各边的长度,使得该树中预先指定的点s成为修改后网络的绝对1-中心(或顶点1-中心)。
在本文中,我们主要研究树的逆1-中心选址问题,即在满足边长调整的上下界约束条件下和在某种度量模的意义下保证总调整费用最小时,修改边长使预先给定的点s成为边长修改后树的绝对1-中心(或顶点1-中心).这里边长调整引起的总费用分别采用了赋权l∞模及和式哈明距离两种计算方式。
对于赋权和哈明距离下的树上逆1-中心问题,我们首先给出了求解哈明距离下的树高降低问题的时间复杂性为O(n2)的算法;然后证明了两树树高平衡问题可以转化为0-1背包问题,从而是NP困难的.在此基础上进一步讨论了逆绝对1-中心问题和逆顶点1-中心问题,它们在拓扑结构不变和改变时都以树高平衡问题为子问题,从而在赋权和哈明距离下的树上逆1-中心问题也是NP困难的。
对于赋权l∞模下的树上逆1-中心问题,由于边长调整后的最长路可能发生改变,因此我们利用二分法来解决树高平衡问题,并给出了时间复杂性为O(nlogn)的算法.在此基础上进一步讨论了逆绝对1-中心问题和逆顶点1-中心问题,给出了它们在拓扑结构不变和改变时各自的算法.具体的结论是:在赋权l∞模下,绝对1-中心选址逆问题在树的拓扑结构不变时,算法的时间复杂性为O(nlogn),在拓扑结构改变时算法的时间复杂性为O(n2logn).逆顶点1-中心问题在树的拓扑结构不变时算法的时间复杂性为O(nlogn),在拓扑结构改变时算法的时间复杂性为O(rvn2logn),其中rv≤n。