四正则图的纵横嵌入优化并行算法*

纵横嵌入术已为超大规模集成电路（VLSI）的平面设计提供了较完备的理论体系,在EREW PRAM(ExclusiveRread and ExclusiveWrite Parallel Random Access Machine)并行计算模型上,使用O((m+n)/ logn)个处理器,时间复杂度为O(logn),对四正则图的纵横嵌入图优化,使图中边的总折数达到最少且所占面积最小。     

基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

一个求图的连通分支的并行算法

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

序贯LSB隐写术的提取攻击

序贯LSB隐写术在载体中通过连续LSB替换嵌入消息,其提取攻击问题本质上是消息嵌入起止点的估计问题。该文建立针对序贯LSB隐写术的提取攻击模型,将提取攻击问题转化为一类排序问题。对嵌入率未知情形,提出计算复杂度为O(n)的提取攻击算法。对嵌入率已知情形,给出计算复杂度为O(2logn)的快速提取攻击算法。实现了对序贯JSteg算法的提取攻击。     

多播3-Omega交换网的设计思想

阐述了具有最佳硬件复杂度且可无阻地在输入/输出间传输任意多播信号的多播3-Omega网的设计思想，设计理念可表述为“置换-复制-置换”，组成形式为“Omega-1+Omega+Omega-1”。它具有O(nlogn)的硬件代价，存储空间和时间复杂度均为O(nlogn)，连接建立时间为(logn)，传输延迟O(logn)，符合Shannon的硬件代价极限标准，具有良好的可实现性。     

最近点问题的三角不等式算法

本文用树结构存贮有限空间的点.然后,设计了一个查找针对已知查询点的最近点的算法——三角不等式算法.整个算法的空间复杂性为O(n);预处理和查询时间复杂性分别为O(n·logn)和O(c·logn), c<相似文献   

可重构造网孔机器上最小生成森林的边更新算法

最小生成森林的边更新在网络路由等方面有着重要的应用价值 .给定 n个结点的无向加权单图 G,该文首先在 n× n的二维可重构造网孔机器上提出了在 O(1)时间内判断 n个结点的无向图的连通性和在 O(logn)时间内求 n个结点的内向树中任一结点到根的路径两个算法 ,并在 n× n× n的三维可重构造网孔机器上提出了 O(1)时间内求 n个结点内向树中任一结点到根的路径的算法 .然后在上述算法的基础上提出了两个 G的最小生成森林的边更新算法 ,一个运行在 n× n的二维可重构造网孔机器上 ,时间复杂度是 O(logn) ,另一个运行在 n× n× n的三维可重构造网孔机器上 ,时间复杂度是 O(1) .     

基于锚点的快速无监督图嵌入

图嵌入降维算法由于其有效性被广泛应用.传统图嵌入算法构造K-Nearest Neighbors(K-NN)图的计算复杂度至少为O(n2 d),其中n为样本数,d为样本维度.在数据量大的情况下,构造K-NN图将非常耗时,因为其计算复杂度与样本数的平方成正比,这将限制图嵌入算法在大规模数据集上的应用.为降低构图过程的计算复...     

双调选择网络及其在多处理器上的双调选择算法

所谓(m,n)选择问题系数指从n个数中选择m个最小(或最大)者的问题.此问题的并行求解目前在网络上已得以实现,而在多处理器系统上却很少被人研究.本文首先基于Batcher的双调归併原理,提出一种比较器数目和延迟级数分别为O(nlog~2m)和O(logn·logm)~(2))的双调选择网络;然后通过观察该网络中数据移动之特点来找出双调选择网络中相继各列枢点之变化规律;最后由此规律给出了一种在n个处理器上可在O(logn·logm)时间步内完成的并行双调选择算法.     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O(n)，总时间复杂度由此降为O(n^2)．     

快速动态优先搜索树的实现及其应用

对形如（x1：x2,[-∞：y]）的二维查询问题,提出一种快速的、易于实现的动态优先搜索树数据结构及其相关算法,采用只在叶节点存储数据的结构,以及在常数时间内实现旋转操作的算法。设n为数据点的个数,k为满足搜索条件的解的个数,则该动态搜索树空间复杂度为O（n）,插入、删除操作的时间复杂度为O（10gn）,搜索复杂度为O（logn＋k）。     

Fully dynamic maintenance of k-connectivity in parallel

Given a graph G=(V, E) with n vertices and m edges, the k-connectivity of G denotes either the k-edge connectivity or the k-vertex connectivity of G. In this paper, we deal with the fully dynamic maintenance of k-connectivity of G in the parallel setting for k=2, 3. We study the problem of maintaining k-edge/vertex connected components of a graph undergoing repeatedly dynamic updates, such as edge insertions and deletions, and answering the query of whether two vertices are included in the same k-edge/vertex connected component. Our major results are the following: (1) An NC algorithm for the 2-edge connectivity problem is proposed, which runs in O(log n log(m/n)) time using O(n^3/4) processors per update and query. (2) It is shown that the biconnectivity problem can be solved in O(log^{2 n} ) time using O(nα(2n, n)/logn) processors per update and O(1) time with a single processor per query or in O(log n log_n/^m) time using O(nα(2n, n)/log n) processors per update and O(logn) time using O(nα(2n, n)/logn) processors per query, where α(.,.) is the inverse of Ackermann's function. (3) An NC algorithm for the triconnectivity problem is also derived, which takes O(log n log_n/^m+logn log log n/α(3n, n)) time using O(nα(3n, n)/log n) processors per update and O(1) time with a single processor per query. (4) An NC algorithm for the 3-edge connectivity problem is obtained, which has the same time and processor complexities as the algorithm for the triconnectivity problem. To the best of our knowledge, the proposed algorithms are the first NC algorithms for the problems using O(n) processors in contrast to Ω(m) processors for solving them from scratch. In particular, the proposed NC algorithm for the 2-edge connectivity problem uses only O(n^3/4) processors. All the proposed algorithms run on a CRCW PRAM     

一种有效的最小生成树并行算法

本文基于三维网孔处理机阵列，运用分而治之策略和数据归约技术在加权无向图上给出了一种新的有效的最小生成树算法。     

A neural-network algorithm for a graph layout problem

We present a neural-network algorithm for minimizing edge crossings in drawings of nonplanar graphs. This is an important subproblem encountered in graph layout. The algorithm finds either the minimum number of crossings or an approximation thereof and also provides a linear embedding realizing the number of crossings found. The parallel time complexity of the algorithm is O(1) for a neural network with n(2) processing elements, where n is the number of vertices of the graph. We present results from testing a sequential simulator of the algorithm on a set of nonplanar graphs and compare its performance with the heuristic of Nicholson.     

图嵌入算法的分布式优化与实现

随着人工智能时代的到来,图嵌入技术被越来越多的用来挖掘图中的信息.然而,现实生活中的图通常很大,因此分布式图嵌入技术得到了广泛的关注,分布式图嵌入算法面临着两大难点：（1）图嵌入算法多种多样,没有一个通用的框架能够描述大部分的算法;（2）现在的分布式图嵌入算法扩展性不足,当处理大图时性能较低,针对以上两个挑战,本文首先提出一个通用的分布式图嵌入框架,具体地,本文将图嵌入算法中的采样流程和训练流程进行解耦,使得框架能够较好的表达多种不同的算法;其次,本文提出了一种基于参数服务器的模型切分嵌入策略,具体地,本文将模型分别切分到计算节点和参数服务器上,同时使用数据洗牌的操作保证计算节点之间没有模型交互,从而大大减少了分布式计算中的通信开销,笔者基于参数服务器实现了一个原型系统,并且用充分的实验证明了在不损失精度的前提下,基于模型切分的策略能够比基线系统取得更好的性能.     

Number of mutual connections in neighborhoods and its application to self-diagnosable systems

This paper gives a set of discriminators (sufficient conditions) to identify the possibility of embedding optimal, highly structured systems on regular graphs for the purpose of self-diagnosis. The discrimination process is only a set of straightforward matrix computations; however, the discriminator is powerful and leads to the result that most of the typical graphs representing interconnection networks such as Cayley graphs can be embedded by the highly structured systems. The highly structured system has an O(|E|) fault-identification algorithm that can diagnose each of the units independently, locally and in any order, where |E| means the cardinality of the set of edges.     

Optimal parallel algorithms for finding proximate points, withapplications

Consider a set P of points in the plane sorted by the x-coordinate. A point p in P is said to be a proximate point if there exists a point q on the x-axis such that p is the closest point to q over all points in P. The proximate point problem is to determine all the proximate points in P. Our main contribution is to propose optimal parallel algorithms for solving instances of size n of the proximate points problem. We begin by developing a work-time optimal algorithm running in O(log log n) time and using n/loglogn Common-CRCW processors. We then go on to show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. In addition to being work-time optimal, our EREW algorithm turns out to also be time-optimal. Our second main contribution is to show that the proximate points problem finds interesting, and quite unexpected, applications to digital geometry and image processing. As a first application, we present a work-time optimal parallel algorithm for finding the convex hull of a set of n points in the plane sorted by x-coordinate; this algorithm runs in O(log log n) time using n/logn Common-CRCW processors. We then show that this algorithm can be implemented to run in O(log n) time using n/logn EREW processors. Next, we show that the proximate points algorithms afford us work-time optimal (resp, time-optimal) parallel algorithms for various fundamental digital geometry and image processing problems