Computing the Greedy Spanner in Near-Quadratic Time

The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in O(n²logn)\ensuremath {\mathcal {O}}(n^{2}\log n) time. Since computing the greedy spanner has an Ω(n ²) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor.     

Parallel quicksort

A parallel version of quicksort on a CRCW PRAM is developed. The algorithm uses n processors and a linear space to sort n keys in the expected time O(log n) with large probability.     

A Fast Algorithm for Image Component Labeling with Local Operators on Mesh Connected Computers

A new parallel algorithm for image component labeling with local operators on SIMD mesh connected computers is presented. This algorithm provides a positive answer to the open question of whether there exists an O(n)-time and O(log n)-space local labeling algorithm on SIMD mesh connected computers. The algorithm uses a pipeline mechanism with stack-like data structures to achieve the lower bound of O(n) in time complexity and O(log n) in space complexity. Additionally, the algorithm has very small multiplicative constants in its complexities by using local parallel-shrink and label-propagate operations.     

Boundary fitting for 2D curve reconstruction

In this paper we present a 3-step algorithm for reconstructing curves from unorganized points: data clustering to filter out the noise, data confining to get the boundary, and region thinning to find the skeleton curve. The method is effective in removing far-from-the-shape noise and in handling a shape of changing density. The algorithm takes O(nlog n) time and O(n) space for a set of n points.     

Computing inversion pair cardinality through partition-based sorting

In this paper, we introduce a new randomized, partition-based algorithm for the problem of computing the number of inversion pairs in an unsorted array of n numbers. The algorithm runs in expected time O(n · log n) and uses O(n) extra space. The expected time analysis of the new algorithm is different from the analyses existing in the literature, in that it explicitly uses inversion pairs. The problem of determining the inversion pair cardinality of an array finds applications in a number of design domains, including but not limited to real-time scheduling and operations research. At the heart of our algorithm is a new inversion pair conserving partition procedure that is different from existing partition procedures such as Hoare-partition and Lomuto-partition. Although the algorithm is not fully adaptive, we believe that it is the first step towards the design of an adaptive, partition-based sorting algorithm whose running time is proportional to the number of inversion pairs in the input.      

Adaptive and efficient mutual exclusion

Summary. This paper presents adaptive algorithms for mutual exclusion using only read and write operations; the performance of the algorithms depends only on the point contention, i.e., the number of processes that are concurrently active during the algorithm execution (and not on n, the total number of processes). Our algorithm has O(k) remote step complexity and O(logk) system response time, wherek is the point contention. The remote step complexity is the maximal number of steps performed by a process where a wait is counted as one step. The system response time is the time interval between subsequent entries to the critical section, where one time unit is the minimal interval in which every active process performs at least one step. The space complexity of this algorithm is O(N logn), where N is the range of processes' names. We show how to make the space complexity of our algorithm depend solely on n, while preserving the other performance measures of the algorithm. Received: March 2001 / Accepted: November 2001     

Improved edge-coloring with three colors

We show an O(1.344ⁿ)=O(2^0.427n) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous O(2^n/2) algorithm of Beigel and Eppstein [R. Beigel, D. Eppstein, 3-coloring in time O(1.3289n), J. Algorithms 54 (2) (2005) 168–204.]. We apply a very natural approach of generating inclusion–maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

Improving a lightweight LZ77 computation algorithm for running faster

Computing the Lempel–Ziv factorization (LZ77) of a string is a key step in many applications. However, at the same time, it constitutes a bottleneck of the entire computation. The investigation of time and space efficient computation of the LZ77 has become an important topic. In this paper, we present a lightweight linear‐time algorithm called LZone for computing the LZ77, which is designed by improvements on the existing linear‐time space efficient LZ77 algorithm BGone for speed acceleration. For an input string T[1..n] over a constant alphabet size of O(1), LZone requires only n words of workspace in addition to the input string and the output factorization, ?logn? bits per word. This is the same space requirement for the algorithm BGone. LZone has two versions, LZoneT and LZoneSA, corresponding to BGoneT and BGoneSA, respectively. Our experimental results show that for computing the LZ77 from an input string T, LZoneT and LZoneSA run at around 26% and 57%, respectively, faster than their counterparts in BGone. Moreover, for computing the LZ77 from the suffix array of T, the speed of LZoneSA is on average twice that of BGoneSA. Copyright © 2015 John Wiley & Sons, Ltd.     

Clamshell Casting

A popular manufacturing technique is clamshell casting, where liquid is poured into a cast and the cast is removed by a rotation once the liquid has hardened. We consider the case where the object to be manufactured is modeled by a polyhedron with combinatorial complexity n of arbitrary genus. The cast consists of exactly two parts and is removed by a rotation around a line in space. The following two problems are addressed: (1) Given a line of rotation l in space, we determine in O(nlog n) time whether there exists a partitioning of the cast into exactly two parts, such that one part can be rotated clockwise around l and the other part can be rotated counterclockwise around l without colliding with the interior of P or the cast. If the problem is restricted further, such a partitioning is only valid when no reflex edge or face of P is perpendicular to l, the algorithm runs in O(n) time. (2) An algorithm running in O(n ⁴log n) time is presented to find all the lines in space that allow a cast partitioning as described above. If we restrict the problem further and find all the lines in space that allow a cast partitioning as described above, such that no reflex edge or face of P is perpendicular to l, the algorithm’s running time becomes O(n ⁴ α(n)). All of the running times are shown to be almost optimal.     

Fully Dynamic Algorithm for Recognition and Modular Decomposition of Permutation Graphs

This paper considers the problem of maintaining a compact representation (O(n) space) of permutation graphs under vertex and edge modifications (insertion or deletion). That representation allows us to answer adjacency queries in O(1) time. The approach is based on a fully dynamic modular decomposition algorithm for permutation graphs that works in O(n) time per edge and vertex modification. We thereby obtain a fully dynamic algorithm for the recognition of permutation graphs.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

求解大规模谱聚类的近似加权核k-means算法

谱聚类将聚类问题转化成图划分问题,是一种基于代数图论的聚类方法.在求解图划分目标函数时,一般利用Rayleigh熵的性质,通过计算Laplacian矩阵的特征向量将原始数据点映射到一个低维的特征空间中,再进行聚类.然而在谱聚类过程中,存储相似矩阵的空间复杂度是O(n²),对Laplacian矩阵特征分解的时间复杂度一般为O(n³),这样的复杂度在处理大规模数据时是无法接受的.理论证明,Normalized Cut图聚类与加权核k-means都等价于矩阵迹的最大化问题.因此,可以用加权核k-means算法来优化Normalized Cut的目标函数,这就避免了对Laplacian矩阵特征分解.不过,加权核k-means算法需要计算核矩阵,其空间复杂度依然是O(n²).为了应对这一挑战,提出近似加权核k-means算法,仅使用核矩阵的一部分来求解大数据的谱聚类问题.理论分析和实验对比表明,近似加权核k-means的聚类表现与加权核k-means算法是相似的,但是极大地减小了时间和空间复杂性.     

Optimal disk merge patterns

Our purpose is to study the optimal way to merge n initially sorted runs, stored on a disk like device, into a unique sorted file. This problem is equivalent to finding a tree with n leaves which minimizes a certain cost function (see Knuth [1]).We shall study some properties of those optimal trees, in the hope of finding efficient ways for constructing them.In particular, if all the initial runs have the same length, an algorithm for constructing the best merge pattern is described ; its running time is proportional to n ² and it requires space proportional to n.A special case is also analyzed in which the problem is solved in time and space proportional to n, and which provides some insight into the asymptotic behaviour of optimal merge trees.     

A polynomial time algorithm for an exact encoding of space containing

We address the problem of collision free navigation of a point robot among polygonal obstacles in a bounded known terrain in two dimensional space. The obstacles could be convex or concave polygons. We consider a combinatorial approach to the problem and focus on partitioning the terrain into distinct regions and encoding these regions. We then build a region-graph whose nodes represent the regions and every pair of neighbouring regions (nodes) are connected by an edge. We propose an o(n ₄) preprocessing algorithm to do this. This converts the problem of navigation from a source point to a destination point into a problem of finding a path in a planar graph from one of its nodes to another in O (n ₂ log n) time. The shortest path is derivable in 0(n ₄) time. The extension of the algorithm for three-dimensional space is also discussed.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

An optimal algorithm for decomposing a window into maximal quadtree blocks

Decomposing a two-dimensional window (i.e., the region specified by the cross product of two closed intervals over a given two-dimensional space) into its maximal quadtree blocks means to find the set of black quadrants that would be obtained by representing the region covered by the window using a quadtree. In this paper we propose an optimal O(n) time algorithm for decomposing a square window of size embedded in an image space of pixel elements, thus improving the O(n log log T) time algorithm of Aref and Samet [2]. As a direct consequence of this new faster algorithm, classical window operations on main memory quadtree based data structures can be solved more efficiently. In particular, we show that the exist and report queries on the incomplete pyramid [1] and on the up-down pyramid [8] can be solved in O(n) time, which is optimal. Received: 1 September 1997 / 28 October 1998     

双向选择排序算法

为丰富O(n²)阶排序算法的种类,以更好地服务于教学科研和日常应用,提出了一种新的排序算法-双向选择排序算法.通过数学方法分析得知:该算法的时间复杂度为O(n²),空间复杂度为O(1).通过实验对比得知:在相同条件下,该算法的运行时间平均为冒泡排序的27%、简单选择排序的62%、直接插入排序的88%.     

Systolic parsing of context-free languages

We report on a new systolic context-free language parsing algorithm. We present both single parse and multiple parse versions of the algorithm. For an input of lengthn the single parse version has a time complexity ofO(n) and a space complexity ofO(n) ². This equals the performance of the most effcient known single parse algorithm. The space complexity of the multiple parse version is also ofO(n) ² while its time complexity is ofO(mn) wherem is the number of differenti parses for the input. This equals the time complexity of the most efficient known multiple parse algorithms and brings an improvenment of a factor of logn over its space complexity.This work was supported by Université de Montréal, the Natural Science Engineering Resarch Council of Canada and the Communittee of Vice-Chancellors and Principals of the Universities of the United Kingdom.     

Using euler partitions to edge color bipartite multigraphs

An algorithm for finding a minimal edge coloring of a bipartite multigraph is presented. The algorithm usesO(V ^1/2 ElogV + V) time andO(E + V) space. It is based on a divide-and-conquer strategy, using euler partitions to divide the graph. A modification of the algorithm for matching is described. This algorithm finds a maximum matching of a regular bipartite graph with all degrees 2ⁿ, inO(E + V) time andO(E + V) space.This work was partially supported by the National Science Foundation under Grant GJ36461.