Hypercube多处理器上图的最优算法 被引量：4

1

作者 梁维发 陈国良 《计算机学报》 EI CSCD 北大核心 1991年第9期641-650,共10页

已知一个无向图G(V,E),|V|=n.本文在SIMD机器-Hype-rcube上提出了计算图的连通分支和最小生成树的两个最优算法.若Hypercu-be由P个处理器组成,则上述两个算法的时间复杂性都是O(n^2/p),1≤p且PlogP≤n.

关键词 多处理器 图 最优算法 互连网络

在线阅读 下载PDF 职称材料

拓扑排序的分布式算法 被引量：1

2

作者 梁维发 唐策善 《计算机研究与发展》 EI CSCD 北大核心 1991年第9期42-45,共4页

本文基于异步通讯的分布式计算模型,对AOE 网的拓扑排序问题,提出了一个分布式算法。设计此算法的关键是使用了一种动态生成树结构。算法的通讯复杂性是O(dm),时间复杂性为O(d^2)。这里d 是网络的直径,m 是网络的通讯链数目,n 是网络中... 本文基于异步通讯的分布式计算模型,对AOE 网的拓扑排序问题,提出了一个分布式算法。设计此算法的关键是使用了一种动态生成树结构。算法的通讯复杂性是O(dm),时间复杂性为O(d^2)。这里d 是网络的直径,m 是网络的通讯链数目,n 是网络中处理机数目(d<n)。 展开更多

关键词 微机 分布式 拓扑排序 算法

在线阅读 下载PDF 职称材料

网孔处理机阵列上最小生成树算法 被引量：1

3

作者 梁维发 唐策善 《计算机学报》 EI CSCD 北大核心 1992年第3期220-225,共6页

已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n^2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计... 已知一加权无向图G(V,E),|V|=n.本文基于网孔处理机阵列,运用分而治之策略和数据归约技术给出了一种新的最小生成树算法.此算法需O(n^2/p)时间,使用了O(p)个处理机(1≤p≤n).当p=n时,此算法仅需O(n)时间和O(n)处理机.而目前基于同一计算模型上此问题的最好算法需O(n)时间和O(n^2)个处理机,因而这里给出的算法在使用处理机数目方面改进了O(n)因子. 展开更多

关键词 并行算法 最小生成树 网孔阵列

在线阅读 下载PDF 职称材料

树网结构上的并行图论算法

4

作者 梁维发 陈国良 《计算机研究与发展》 EI CSCD 北大核心 1991年第1期1-8,共8页

本文在分析树网结构的同时,发现了树网上一特殊的传播规律。利用此规律我们给出了在n 阶树网(n×n 个叶结点)上O(nlogn)步的n 阶矩阵乘法算法,此算法具有广泛的应用。运用它可有效地模拟二维网孔模型上一类算法。最后,我们给出了在n... 本文在分析树网结构的同时,发现了树网上一特殊的传播规律。利用此规律我们给出了在n 阶树网(n×n 个叶结点)上O(nlogn)步的n 阶矩阵乘法算法,此算法具有广泛的应用。运用它可有效地模拟二维网孔模型上一类算法。最后,我们给出了在n 阶树网上求n 个顶点无向图的快速桥算法,其时间复杂性为O(log^3n)。 展开更多

关键词 树网结构 并行 图论 算法

在线阅读 下载PDF 职称材料

并行图论算法研究进展 被引量：13

5

作者 陈国良 梁维发 沈鸿 《计算机研究与发展》 EI CSCD 北大核心 1995年第9期1-16,共16页

在这篇综述文章中，我们将重点介绍并行图论算法近年来的发展概况及主要成果，并给出一些可能的发展方向。具体内容包括：基于共享存储模型上的图搜索技术、连通分支及最小生成树算法、增值并行图论算法、最短路径算法、极大独立集算法... 在这篇综述文章中，我们将重点介绍并行图论算法近年来的发展概况及主要成果，并给出一些可能的发展方向。具体内容包括：基于共享存储模型上的图搜索技术、连通分支及最小生成树算法、增值并行图论算法、最短路径算法、极大独立集算法、极大匹配与最大匹配算法、图着色算法、求欧拉回路及哈密尔顿回路算法、图同构算法、图ｋ连通算法以及最大流最小割算法等。 展开更多

关键词 并行图论 算法 图论

在线阅读 下载PDF 职称材料

一个求图的连通分支的并行算法 被引量：1

6

作者 唐策善 梁维发 《软件学报》 EI CSCD 北大核心 1993年第4期61-65,F004,共6页

已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log^2n)时间、O(n^2/logn)处理器;而在SIMD—CRC... 已知一个无向图G(V,E),|V|=n,|E|=m,本文基于SIMD共享存贮模型,运用数据在图中快速传播原理,建议了一个新的求图的连通分支算法,具体来讲,在SIMD—CREW共享存贮模型上,求图的连通分支需O(log^2n)时间、O(n^2/logn)处理器;而在SIMD—CRCW共享存贮模型上需O(logn)时间、O(n^2)处理器,建议的算法同著名的Hirschberg算法相比,其主要差别表现在:1)采用的求解方法不同;2)建议的算法简单易懂;3)在某些实际网络如树网上,实现建议的算法有较好的时间复杂性。 展开更多

关键词 求图 连通分支 并行算法

在线阅读 下载PDF 职称材料

分治策略设计并行算法 被引量：1

7

作者 唐策善 梁维发 《微电子学与计算机》 CSCD 北大核心 1990年第4期17-20,共4页

本文通过给出适应D&C策略的几种典型体系结构,用一些具体例子说明D&C策略在设计并行算法方面的重要性.

关键词 分治法 并行算法 计算机

在线阅读 下载PDF 职称材料

找K个最小生成树的并行算法

8

作者 唐策善 梁维发 《中国科学技术大学学报》 CAS CSCD 北大核心 1990年第4期464-471,共8页

基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log^2n+Klogn~*)时间及O(n^2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klo... 基于SIMD 机器——一种可以同时读但不可同时写的共享计算模型(CREW-PRAM)给出了找K 个最小生成树的并行算法,此算法需O(log^2n+Klogn~*)时间及O(n^2)处理器;而基于可以同时读、写的更强计算模型(CRCW-PRAM),求K 个最小生成树仅需O(Klogn)时间及O(n^2)处理器,这里n 是图的顶点数. 展开更多

关键词 并行算法 最小生成树 图论

在线阅读 下载PDF 职称材料

二分图最大匹配问题的分布式算法

9

作者 唐策善 梁维发 《计算机工程与应用》 CSCD 北大核心 1990年第10期48-53,共6页

本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n^2+m))、时间复杂性为 O(n^3);第二个算法的通讯复杂性为O(n^(1/2)(n^2+m))、时间复杂性为O(n^(5/2)),这里n和m分别为二分图... 本文基于异步通讯网络,对二分图最大匹配问题,建议了两个分布式算法。其中第一个简单算法的通讯复杂性为O(n(n^2+m))、时间复杂性为 O(n^3);第二个算法的通讯复杂性为O(n^(1/2)(n^2+m))、时间复杂性为O(n^(5/2)),这里n和m分别为二分图的结点个数及边的数目。关于这一问题的分布式算法目前尚未见诸报导,这里建议的算法很可能是此问题的第一个分布式算法。 展开更多

关键词 二分图 最大匹配 分布式算法

在线阅读 下载PDF 职称材料

关于区间图的一些有效并行算法

10

作者 唐策善 梁维发 《高校应用数学学报（A辑）》 CSCD 北大核心 1989年第4期534-540,共7页

本文基于SIMD-CREW-PRAM一种可同时读但不可同时写的共享计算模型,给出了有关区间图的一些有效的并行算法。如找最大加权集团,最小集团覆盖,等权区间图的最大独立集及最小支配集,真区间图的哈密顿回路及最小带宽。所有这些算法都是最优... 本文基于SIMD-CREW-PRAM一种可同时读但不可同时写的共享计算模型,给出了有关区间图的一些有效的并行算法。如找最大加权集团,最小集团覆盖,等权区间图的最大独立集及最小支配集,真区间图的哈密顿回路及最小带宽。所有这些算法都是最优的,其时间复杂性为O(logn)和处理器数为O(n)。 展开更多

关键词 区间图 并行算法 最大加权集团

在线阅读 下载PDF 职称材料

认知无线电网络频谱分配与协作集划分算法 被引量：6

11

作者 杨威 班冬松 +1 位作者 梁维发 窦文华 《软件学报》 EI CSCD 北大核心 2012年第1期122-139,共18页

针对协作认知无线电网络中较为复杂的多主用户与多次级用户共存场景,提出联合频谱分配与协作集划分问题,并将该问题形式化描述为整数0-1非线性规划问题,证明其是NP-hard的.首先,设计了集中式的遗传算法CGA(centralized genetic algorit... 针对协作认知无线电网络中较为复杂的多主用户与多次级用户共存场景,提出联合频谱分配与协作集划分问题,并将该问题形式化描述为整数0-1非线性规划问题,证明其是NP-hard的.首先,设计了集中式的遗传算法CGA(centralized genetic algorithm)对问题求解,对该算法进行齐次有限马尔可夫链建模并对其全局收敛性进行了分析;随后,提出了一种包含两阶段的分布式遗传算法DGA(distributed genetic algorithm),包括基于最小支配集的分簇与频谱预分配阶段和簇间协作集协商与簇内适应值精化阶段.此外,还提出一种快速收敛的DGA算法(fast-convergent DGA,简称FDGA)缩短分布式算法运行时间.仿真实验结果表明,根据能反映出算法性能的适应值结果对各算法进行比较:(1)小规模网络下CGA获得的解平均为通过穷举算法得到的最优值的92%;(2)随着网络规模的扩大,由于CGA搜索空间增大,DGA,FDGA在达到相同停机条件时获得的适应值比CGA提高约20%;(3)与DGA相比,FDGA虽能得到与DGA相近的结果,但却大大缩短了算法收敛的时间,更适应于大规模网络应用. 展开更多

关键词 协作认知无线电网络 频谱分配 协作集划分 分布式遗传算法 有限齐次马尔可夫链

在线阅读 下载PDF 职称材料

AOE网的并行算法

12

作者 唐策善 梁维发 《计算数学》 CSCD 北大核心 1991年第2期113-120,共8页

在并行图论算法中,有向图G(V,E)的重要应用之一是边表示活动的网(即AOE网).本文研究AOE网的并行算法.假定AOE网是一个带权的有向无环图,其中顶点i∈V表示事件,有向边<i,j>∈E表示活动,权w(i,j)表示活动的持续时间.为不失一般性,... 在并行图论算法中,有向图G(V,E)的重要应用之一是边表示活动的网(即AOE网).本文研究AOE网的并行算法.假定AOE网是一个带权的有向无环图,其中顶点i∈V表示事件,有向边<i,j>∈E表示活动,权w(i,j)表示活动的持续时间.为不失一般性,进一步假定:V={1,2,…,n},起始点s=1,终止点t=n。 本文是在单指令流多数据流(SIMD)机器上研究并行算法.假定机器有一个无限大的共享主存贮器,有f(n)个处理器(其中f(n)是n的多项式)。 展开更多

关键词 并行算法 AOE网 排序 矩阵乘法

原文传递