论文部分内容阅读
选址理论是研究在给定的网络中如何确定满足特定条件“设施”的最佳位置的组合优化理论,在交通运输、计算机网络、通信工程等领域有着广泛而重要的应用.
传统选址理论中往往把“设施”抽象为点.然而,在许多实际应用中,由于设施所占的空间太大而不能仅仅看作一个点.为了更好的研究这类设施,很多研究者把这种不能看作是单个点的设施抽象成网络中的路或者是树状网络.目前,关于网络中路或树状网络设施的最佳位置的衡量标准主要基于最小(大)离心率、最小(大)距离总和等(所谓离心率最小指从“设施”到最远结点的距离最小;距离总和最小是指从“设施”到所有结点的距离总和最小).
本文主要基于最小离心率、最小距离总和两个优化标准研究如下几个选址问题:树状网络中含k个叶结点的离心率最小的子树(即所谓树的k-树中心问题);树状网络中含k个叶结点的距离总和最小的子树(即所谓树的k-树核问题);含k个叶结点的、直径至多为l的、离心率最小的子树(即所谓树的(k,l)-中心问题);至多含k个叶结点的、直径至多为l的、距离总和最小的子树(即所谓树的k-树核问题).
具体成果如下:
(1)用EREWPRAM模型构造了一个k-树中心的并行算法,其算法时间复杂度是用O(n)个处理器,执行时间为O(logn),降低了Wang(Findingak-treecoreandak-treecenterofatreenetworkinparallel.IEEETrans.Par.andDis.Sys.,1998)给出的k-树中心并行算法.
(2)利用欧拉回路和树收缩方法,提出了一个有效的k-树核并行算法,执行EREWPRAM模型,算法时间复杂度是用O(n)个处理器,执行时间为O(logn).改进了Wang给出的k-树核并行算法Wang(Findingak-treecoreandak-treecenterofatreenetworkinparallel.IEEETrans.Par.andDis.Sys.,1998),并降低了时间复杂度.
(3)在k-树中心和k-树核的算法基础上,提出了(k,l)-核和(k,l)-中心的有效并行算法.这两个算法运行在EREWPRAM模型上,时间复杂度是用O(n)个处理器,执行时间为O(logn).