在l∞模和哈明距离下的树上的逆1-中心问题

来源 :东南大学 | 被引量 : 0次 | 上传用户:chenzeqian
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
树上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。
其他文献
本文基于有限差分法对两类非线性Schrodinger方程建立差分格式。  第一章给出了本文的研究背景和研究意义,并详列文章的结构及主要内容。  第二章,首先对二维非线性Schrodi
集合差系统(DSS)是由码字同步问题所引发的一个组合问题.解决码字同步问题的一种方法是构造无逗码,即构造码C(C-)Fup使得此码中的任意两个码字(可以相同)的邻接都不是码C中的
本文是为一类伪线性方程组--p-Laplacian方程组多解问题的数值计算设计算法。p-Laplacian方程组在非牛顿流体问题,非线性弹性问题及冰川学等研究中有应用,并且在方程的理论研究
本文分析了在ad hoc网络中TCP协议的主要缺陷,并对目前提出的几种改进方案进行了比较分析,最后给出了结论和研究方向.
期刊
设p,P1,P2为奇素数,q是一个素数方幂.并且(p,q)=1,(P1,q)=1,(P2,q)=1.m,m1,m,是正整数.本文中从生成多项式的角度采用矩阵的方法分别确定了GF(q)上码长为2pm和码长为pm11 pm2