An O(n log n) algorithm for finding all repetitions in a string

Any nonempty string of the form xx is called a repetition. An O(n log n) algorithm is presented to find all repetitions in a string of lenght n. The algorithm is based on a linear algorithm to find all the new repetitions formed when two strings are concatenated. This linear algorithm is possible because new repetitions of equal length must occur in blocks with consecutive starting positions. The linear algorithm uses a variation of the Knuth-Morris-Pratt algorithm to find all partial occurrences of a pattern within a text string. It is also shown that no algorithm based on comparisons of symbols can improve O(n log n). Finally, some open problems and applications are suggested.     

An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

In this paper we present algorithms, which given a circular arrangement of n uniquely numbered processes, determine the maximum number in a distributive manner. We begin with a simple unidirectional algorithm, in which the number of messages passed is bounded by 2 n log n + O(n). By making several improvements to the simple algorithm, we obtain a unidirectional algorithm in which the number of messages passed is bounded by 1.5nlogn + O(n). These algorithms disprove Hirschberg and Sinclair's conjecture that O(n²) is a lower bound on the number of messages passed in undirectional algorithms for this problem. At the end of the paper we indicate how our methods can be used to improve an algorithm due to Peterson, to obtain a unidirectional algorithm using at most 1.356nlogn + O(n) messages. This is the best bound so far on the number of messages passed in both the bidirectional and unidirectional cases.     

Numerical enclosure for each eigenvalue in generalized eigenvalue problem

An algorithm for enclosing all eigenvalues in generalized eigenvalue problem Ax=λBx is proposed. This algorithm is applicable even if A∈C^n×n is not Hermitian and/or B∈C^n×n is not Hermitian positive definite, and supplies nerror bounds while the algorithm previously developed by the author supplies a single error bound. It is proved that the error bounds obtained by the proposed algorithm are equal or smaller than that by the previous algorithm. Computational cost for the proposed algorithm is similar to that for the previous algorithm. Numerical results show the property of the proposed algorithm.     

Calculation of the discrepancy of a finite set of points in the unit n-cube

An algorithm for calculating the discrepancy of finitely many points in the unit n-cube [0, 1]ⁿ is suggested. This algorithm is easy to program. For 2 ≤ n ≤ 4, the suggested algorithm is significantly faster than Bundschuh and Zhu’s algorithm. For larger n, whether this algorithm is faster depends on the number of points.     

Efficient algorithms for computing the maximum distance between two finite planar sets

An 0(n log n) algorithm is presented for computing the maximum euclidean distance between two finite planar sets of n points. When the n points form the vertices of simple polygons this complexity can be reduced to 0(n). The algorithm is empirically compared to the brute-force method as well as an alternate 0(n²) algorithm. Both the 0(n log n) and 0(n²) algorithms run in 0(n) expected time for many underlying distributions of the points. An ?-approximate algorithm can be obtained that runs in $\text{0(n +}\text{1}\text{?}\text{)}$ worst-case time.     

Optimal algorithms to compute the closure of a set of iso-rectangles

Three varieties of the closure of a set of iso-(oriented) rectangles, i.e., rectilin-early-oriented rectangles, are introduced. These are uni-directional, diagonal, and rectangular closure. First a strong decomposition theorem for diagonal closure in terms of uni-directional closure is proved. Then time and space optimal algorithms to compute uni-directional and diagonal closure, each running in O(nlogn) time and O(n) space, are described. An O(nlogn) time and space algorithm for rectangular closure is also described. The algorithm for diagonal closure has applications in database concurrency control: an O(nlogn) time and O(n) space algorithm for testing for safety and detecting deadlocks in locked transaction systems is obtained.     

The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n²) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.     

Parallel solution of certain Toeplitz least-squares problems

We describe a systolic algorithm for solving a Toeplitz least-squares problem of special form. Such problems arise, for example, when Volterra convolution equations of the first kind are solved by regularization. The systolic algorithm is based on a sequential algorithm of Eldén, but we show how the storage requirements of Eldén's algorithm can be reduced from O(n²) to O(n). The sequential algorithm takes time O(n²); the systolic algorithm takes time O(n) using a linear systolic array of O(n) cells. We also show how large problems may be decomposed and solved on a small systolic array.     

An O(n) algorithm for quadratic knapsack problems

An algorithm is presented which solves bounded quadratic optimization problems with n variables and one linear constraint in at most O(n) steps. The algorithm is based on a parametric approach combined with well-known ideas for constructing efficient algorithms. It improves an O(n log n) algorithm which has been developed for a more restricted case of the problem.     

An optimal parallel connectivity algorithm

A synchronized parallel algorithm of depth O(n²/p) for p (≤n²/log²n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.     

The measure problem for rectangular ranges in d-space

Klee recently posed the question: find an efficient algorithm for computing the measure of a set of n intervals on the line, and the analog for n hyperrectangles (ranges) in d-space. The one-dimensional case is easily solved in O(n log n) and Bentley has proved an O(n^d?1log n) algorithm for dimension d ≥ 2. We present an algorithm for Klee's measure problem that has a worst-case running time of only O(n^d?1) for d?3. While Bentley's algorithm is based on segment trees and requires only linear storage for any dimension, the new method is based on quad-trees and requires quadratic storage for d > 2.     

An optimal contour algorithm for iso-oriented rectangles

Given a set of n iso-oriented rectangles in 2-space we describe an algorithm which determines the contour of their union in O(n log n + p) time and O(n + p) space, where p is the number of edges in the contour. This performance is time-optimal. The space requirements are the same as in the best previously known algorithm. We achieve this by introducing a new data structure, the contracted segment tree, which is a non-trivial modification of the well known segment tree. If only the pieces of the contour are to be reported then this approach yields a time- and space-optimal algorithm.     

Fast solution of toeplitz systems of equations and computation of Padé approximants

We present two new algorithms, ADT and MDT, for solving order-n Toeplitz systems of linear equations Tz = b in time O(n log²n) and space O(n). The fastest algorithms previously known, such as Trench's algorithm, require time $\text{Ω(n}{}^2\text{)}$ and require that all principal submatrices of T be nonsingular. Our algorithm ADT requires only that T be nonsingular. Both our algorithms for Toeplitz systems are derived from algorithms for computing entries in the Padé table for a given power series. We prove that entries in the Padé table can be computed by the Extended Euclidean Algorithm. We describe an algorithm EMGCD (Extended Middle Greatest Common Divisor) which is faster than the algorithm HGCD of Aho, Hopcroft and Ullman, although both require time O(n log²n), and we generalize EMGCD to produce PRSDC (Polynomial Remainder Sequence Divide and Conquer) which produces any iterate in the PRS, not just the middle term, in time O(n log²n). Applying PRSDC to the polynomials U₀(x) = x²ⁿ⁺¹ and U₁(x) = a₀ + a₁x + … + a_2nx²ⁿ gives algorithm AD (Anti-Diagonal), which computes any (m, p) entry along the antidiagonal m + p = 2n of the Padé table for U₁ in time O(n log²n). Our other algorithm, MD (Main-Diagonal), computes any diagonal entry (n, n) in the Padé table for a normal power series, also in time O(n log²n). MD is related to Schönhage's fast continued fraction algorithm. A Toeplitz matrix T is naturally associated with U₁, and the (n, n) Padé approximation to U₁ gives the first column of T^?1. We show how a formula due to Trench can be used to compute the solution z of Tz = b in time O(n log n) from the first row and column of T^?1. Thus, the Padé table algorithms AD and MD give O(n log²n) Toeplitz algorithms ADT and MDT. Trench's formula breaks down in certain degenerate cases, but in such cases a companion formula, the discrete analog of the Christoffel-Darboux formula, is valid and may be used to compute z in time O(n log²n) via the fast computation (by algorithm AD) of at most four Padé approximants. We also apply our results to obtain new complexity bounds for the solution of banded Toeplitz systems and for BCH decoding via Berlekamp's algorithm.     

A cumulative not-first/not-last filtering algorithm in O(n 2log(n))

In cumulative and disjunctive constraint-based scheduling, the resource constraint is enforced by several filtering rules. Among these rules, we have (extended) edge-finding and not-first/not-last rules. The not-first/not-last rule detects tasks that cannot run first/last relatively to a set of tasks and prunes their time bounds. In this paper, it is presented a sound O (n ² log n) algorithm for the cumulative not-first/not-last rule where n is the number of tasks. This algorithm reaches the same fix point as previous not-first/not-last algorithms, although it may take additional iterations to do so. The worst case complexity of this new algorithm for the maximal adjustment is the same as our previous complete O (n ²|H| log n) not-first/not-last algorithm [7] where |H| is the maximum between the number of distinct earliest completion and latest start times of tasks. But, experimental results on benchmarks from the Project Scheduling Problem Library (PSPLib) and the Baptiste and Le Pape data set (BL) suggest that the new not-first/not-last algorithm has a substantially reduced runtime. Furthermore, the results demonstrate that in practice the new algorithm rarely requires more propagations than previous not-first/not-last algorithms.     

An O(nlogn) randomizing algorithm for the weighted euclidean 1-center problem

A randomizing algorithm for the weighted Euclidean 1-center problem is presented. The algorithm is shown to run on any problem in O(nlogn) time with high probability.     

Finding the smallest triangles containing a given convex polygon

For a given convex n-gon P an O(n log²n) algorithm finds all local minima (with respect to area) among the triangles containing P. No areas are computed, for the algorithm is based on a simple geometric characterization of the local minima.     

On some algorithmic problems regarding the hairpin completion

We consider a few algorithmic problems regarding the hairpin completion. The first problem we consider is the membership problem of the hairpin and iterated hairpin completion of a language. We propose an O(nf(n)) and O(n²f(n)) time recognition algorithm for the hairpin completion and iterated hairpin completion, respectively, of a language recognizable in O(f(n)) time. We show that the n factor is not needed in the case of hairpin completion of regular and context-free languages. The n² factor is not needed in the case of iterated hairpin completion of context-free languages, but it is reduced to n in the case of iterated hairpin completion of regular languages. We then define the hairpin completion distance between two words and present a cubic time algorithm for computing this distance. A linear time algorithm for deciding whether or not the hairpin completion distance with respect to a given word is connected is also discussed. Finally, we give a short list of open problems which appear attractive to us.     

An efficient pram algorithm for maximum-weight independent set on permutation graphs

An efficient parallel algorithm is presented to find a maximum weight independent set of a permutation graph which takesO (logn) time usingO (n ²/logn) processors on an EREW PRAM, provided the graph has at mostO (n) maximal independent sets. The best known parallel algorithm takesO (log² n) time andO (n ³/logn) processors on a CREW PRAM.     

Principal minors, Part I: A method for computing all the principal minors of a matrix

An order O(2ⁿ) algorithm for computing all the principal minors of an arbitrary n × n complex matrix is motivated and presented, offering an improvement by a factor of n³ over direct computation. The algorithm uses recursive Schur complementation and submatrix extraction, storing the answer in a binary order. An implementation of the algorithm in MATLAB® is also given and practical considerations are discussed and treated accordingly.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.