无存储器冲突的并行快速排序算法*

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．     

半动态矩形交查询算法

本文讨论了动态矩形交查询算法.文中介绍了两个半动态矩形查询的新算法，它们分别基于一维数据结构和二维数据结构.一维查询算法的查询时间复杂度是O（logM＋k′），更新时间复杂度是O（logMlogn），空间复杂度是O（nlogM/）.二维查询算法的查询时间复杂度是O（log²M＋k），更新时间复杂度是O（log²Mlogn），空间复杂度是O（nlog²M）.本文分别实现了这两个算法，通过对它们的性能进行比较，发现一维查询算法是一种高效、实用的算法.     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

虫孔路由Mesh上的连通分量算法及其应用

用倍增技术在带有Wormhole路由技术的n×n二维网孔机器上提出了时间复杂度为O(log²n)的连通分量和传递闭包并行算法,并在此基础上提出了一个时间复杂度为O(log³n)的最小生成树并行算法.这些都改进了Store-and-Forward路由技术下的时间复杂度下界O(n).同其他运行在非总线连接分布式存储并行计算机上的算法相比,此连通分量和传递闭包算法的时间复杂度是最优的.     

数据仓库系统中层次式Cube存储结构

区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(log^dn),综合性能为O((logn)^2d)(使用C_qC_u模型)或O(K(logn)^d)(使用C_qn_q+C_un_u模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构.     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

一种高效频繁子图挖掘算法

由于在频繁项集和频繁序列上取得的成功,数据挖掘技术正在着手解决结构化模式挖掘问题--频繁子图挖掘.诸如化学、生物学、计算机网络和WWW等应用技术都需要挖掘此类模式.提出了一种频繁子图挖掘的新算法.该算法通过对频繁子树的扩展,避免了图挖掘过程中高代价的计算过程.目前最好的频繁子图挖掘算法的时间复杂性是O(n³·2ⁿ),其中,n是图集中的频繁边数.提出算法的时间复杂性是O〔2ⁿ·n^2.5／logn〕,性能提高了O(√n·logn)倍.实验结果也证实了这一理论分析.     

一类实际网络中的最小截算法

讨论了节点和边都有容量限制的无向平面网络中的两点间的最小截问题.传统方法是把节点和边都有容量的网络中的最小截问题转化为只有边有容量的问题,但该方法用在平面网络时不能保持网络的平面性,因此网络的平面性不能得到利用.使用传统方法的计算时间为O(n²logn)(其中n为网络的节点数).给出了可以充分利用网络平面性的方法.对源和汇共面的s-t平面网络,把最小截问题转化为平面图上两点间的最短路径问题,从而可以得到O(n)时间的算法;对一般的平面网络,给出了新的将节点和边都有容量的问题转化为仅边有容量问题的方法,这种转化方法不破坏网络的平面性,从而可以利用平面网络中仅边有容量问题的计算方法,使原问题在O(nlogn)时间内获得解决.     

矩阵条件数及高斯算法平滑分析的进一步研究

算法的复杂度平滑分析是对许多算法在实际应用中很有效但其最坏情况复杂度却很糟这一矛盾给出的更合理的解释.高性能计算机被广泛用于求解大规模线性系统及大规模矩阵的分解.求解线性系统的最简单且容易实现的算法是高斯消元算法(高斯算法).用高斯算法求解n个方程n个变量的线性系统所需要的算术运算次数为O(n³).如果这些方程中的系数用m位表示,则最坏情况下需要机器位数mn位来运行高斯算法.这是因为在消元过程中可能产生异常大的中间项.但大量的数值实验表明,在实际应用中,需要如此高的精度是罕见的.异常大的矩阵条件数和增长因子是导致矩阵A病态,继而导致解的误差偏大的主要根源.设-A为任意矩阵,A是-A受到微小幅度的高斯随机扰动所得到的随机矩阵,方差σ²≤1.Sankar等人对矩阵A的条件数及增长因子进行平滑分析,证明了Pr[K(A)≥α]≤(3.64n(1+4√log(α)))/ασ.在此基础上证明了运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度为m+71og₂(n)+3log₂(1/σ)+log₂log₂n+7.在上述结果的证明过程中存在错误,将其纠正后得到以下结果:m+71og₂n+3log₂(1/σ)+4√2+log₂n+log₂(1/σ)+7.367.通过构造两个分别关于矩阵范数和随机变量乘积的不等式,将关于矩阵条件数的平滑分析结果简化到Pr[K(A)≥α]≤(6√2n²)/α·σ.部分地解决了Sankar等人提出的猜想:Pr[K(A)≥α]≤O(n/α·σ).并将运行高斯算法输出具有m位精度的解所需机器位数的平滑复杂度降低到m+81og₂n+3log₂(1/σ)+7.实验结果表明,所得到的平滑复杂度更好.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.     

Efficient parallel and sequential algorithms for 4-coloring perfect planar graphs

We present an efficient algorithm for 4-coloring perfect planar graphs. The best previously known algorithm for this problem takesO(n ^3/2) sequential time, orO(log⁴ n) parallel time withO(n³) processors. The sequential implementation of our algorithm takesO(n logn) time. The parallel implementation of our algorithm takesO(log³ n) time withO(n) processors on a PRAM.

     

Parallel algorithms for arrangements

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds ofO (logn log^* n) time andn ²/logn processors. We generalize this to obtain anO (logn log^* n)-time algorithm usingn ^d /logn processors for solving the problem ind dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement ofn lines on-line, in which each insertion is done in optimalO (logn) time usingn/logn processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.This work was supported by the National Science Foundation, under Grants CCR-8657562 and CCR-8858799, NSF/DARPA under Grant CCR-8907960, and Digital Equipment Corporation. A preliminary version of this paper appeared at the Second Annual ACM Symposium on Parallel Algorithms and Architectures [3].     

An optimal speed-up parallel algorithm for triangulating simplicial point sets in space

Previous research on developing parallel triangulation algorithms concentrated on triangulating planar point sets.O(log³ n) running time algorithms usingO(n) processors have been developed in Refs. 1 and 2. Atallah and Goodrich⁽³⁾ presented a data structure that can be viewed as a parallel analogue of the sequential plane-sweeping paradigm, which can be used to triangulate a planar point set inO(logn loglogn) time usingO(n) processors. Recently Merks⁽⁴⁾ described an algorithm for triangulating point sets which runs inO(logn) time usingO(n) processors, and is thus optimal. In this paper we develop a parallel algorithm for triangulating simplicial point sets in arbitrary dimensions based on the idea of the sequential algorithm presented in Ref. 5. The algorithm runs inO(log² n) time usingO(n/logn) processors. The algorithm hasO(n logn) as the product of the running time and the number of processors; i.e., an optimal speed-up.     

Parallel algorithms for minimal spanning trees of directed graphs

The main results of this paper are efficient parallel algorithms, MSP and LOCATE, for computing minimal spanning trees and locating minimal paths in directed graphs, respectively. Algorithm MSP has time complexityO(log³ n) usingO(n ³/logn) processors, while LOCATE has time complexityO(logn) usingO(n ²) processors. Algorithm MSP is derived from sequential algorithms, when the unbounded parallelism model is used.     

Expected parallel time and sequential space complexity of graph and digraph problems

This paper determines upper bounds on the expected time complexity for a variety of parallel algorithms for undirected and directed random graph problems. For connectivity, biconnectivity, transitive closure, minimum spanning trees, and all pairs minimum cost paths, we prove the expected time to beO(log logn) for the CRCW PRAM (this parallel RAM machine allows resolution of write conflicts) andO(logn · log logn) for the CREW PRAM (which allows simultaneous reads but not simultaneous writes). We also show that the problem of graph isomorphism has expected parallel timeO(log logn) for the CRCW PRAM andO(logn) for the CREW PRAM. Most of these results follow because of upper bounds on the mean depth of a graph, derived in this paper, for more general graphs than was known before.For undirected connectivity especially, we present a new probabilistic algorithm which runs on a randomized input and has an expected running time ofO(log logn) on the CRCW PRAM, withO(n) expected number of processors only.Our results also improve known upper bounds on the expected space required for sequential graph algorithms. For example, we show that the problems of finding connected components, transitive closure, minimum spanning trees, and minimum cost paths have expected sequential spaceO(logn · log logn) on a deterministic Turing Machine. We use a simulation of the CRCW PRAM to get these expected sequential space bounds.This research was supported by National Science Foundation Grant DCR-85-03251 and Office of Naval Research Contract N00014-80-C-0647.This research was partially supported by the National Science Foundation Grants MCS-83-00630, DCR-8503497, by the Greek Ministry of Research and Technology, and by the ESPRIT Basic Research Actions Project ALCOM.     

PARALLEL INCREMENTAL ALGORITHMS FOR ANALYZING ACTIVITY NETWORKS

This paper presents parallel incremental algorithms for analyzing activity networks. The start-over algorithm used for this problem is a modified version of an algorithm due to Chaudhuri and Ghosh (BIT 26 (1986), 418-429). The computational model used is a shared memory single-instruction stream, multiple-data stream computer that allows both read and write conflicts. It is shown that the incremental algorithms for the event and activity insertion problems both require only O(loglogn) parallel time, in contrast to O(logn log logn) parallel time for the corresponding start-over algorithm.     

An optimal parallel algorithm for triangulating a set of points in the plane

This paper presents an optimal parallel algorithm for triangulating an arbitrary set ofn points in the plane. The algorithm runs inO(logn) time usingO(n) space andO(_n) processors on a Concurrent-Read, Exclusive-Write Parallel RAM model (CREW PRAM). The parallel lower bound on triangulation is (logn) time so the best possible linear speedup has been achieved. A parallel divide-and-conquer technique of subdividing a problem into subproblems is employed.     

Efficient parallel algorithms forr-dominating set andp-center problems on trees

We develop efficient parallel algorithms for ther-dominating set and thep-center problems on trees. On a concurrent-read exclusive-write PRAM, our algorithm for ther-dominating set problem runs inO(logn log logn) time withn processors. The algorithm for thep-center problem runs inO(log² n log logn) time withn processors.Xin He was supported in part by an Ohio State University Presidential Fellowship, and by the Office of Research and Graduate Studies of Ohio State University. Yaacov Yesha was supported in part by the National Science Foundation under Grant No. DCR-8606366.