On the multisearching problem for hypercubes

In this paper we give improved bounds for the multisearch problem on a hypercube. This is a parallel search problem where the elements in the structure S to be searched are totally ordered, but where it is not possible to compare in constant time any two given queries q and q′. More precisely, we are given on a n-processor hypercube a sorted n-element sequence S, and a set Q of n queries, and we need to find for each query q Q its location in the sorted S. We present an improved algorithm for the multisearch problem, one that takes O(log n(log log n)³) time on a n-processor hypercube. This problem is fundamental in computational geometry, for example it models planar point location in a slab. We give as application a trapezoidal decomposition algorithm with the same time complexity on a n log n-processor hypercube. The hypercube model for which we claim our bounds is the standard one, SIMD, with O(1) memory registers per processor, and with one-port communication. Each register can store O(log n) bits, so that a processor knows its ID.     

Approximating geometric bottleneck shortest paths

In a geometric bottleneck shortest path problem, we are given a set S of n points in the plane, and want to answer queries of the following type: given two points p and q of S and a real number L, compute (or approximate) a shortest path between p and q in the subgraph of the complete graph on S consisting of all edges whose lengths are less than or equal to L. We present efficient algorithms for answering several query problems of this type. Our solutions are based on Euclidean minimum spanning trees, spanners, and the Delaunay triangulation. A result of independent interest is the following. For any two points p and q of S, there is a path between p and q in the Delaunay triangulation, whose length is less than or equal to 2π/(3cos(π/6)) times the Euclidean distance |pq| between p and q, and all of whose edges have length at most |pq|.     

On random cartesian trees

Cartesian trees are binary search trees in which the nodes exhibit the heap property according to a second (priority) key. If the search key and the priority key are independent, and the trees is built based on n independent copies, Cartesian trees basically behave like ordinary random binary search trees. In this article, we analyze the expected behavior when the keys are dependent: in most cases, the expected search, insertion, and deletion times are Φ(√n). We indicate how these results can be used in the analysis of divide-and-conguer algorithms for maximal vectors and convex hulls. Finally, we look at distributions for which the expected time per operation grows like n^a for a ?[1/2, 1]. © 1994 John Wiley & Sons, Inc.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

Some typical properties of large AND/OR Boolean formulas

In this paper typical properties of large random Boolean AND/OR formulas are investigated. Such formulas with n variables are viewed as rooted binary trees chosen from the uniform distribution of all rooted binary trees on m nodes, where n is fixed and m tends to infinity. The leaves are labeled by literals and the inner nodes by the connectives AND/OR, both uniformly at random. In extending the investigation to infinite trees, we obtain a close relation between the formula size complexity of any given Boolean function f and the probability of its occurrence under this distribution, i.e., the negative logarithm of this probability differs from the formula size complexity of f only by a polynomial factor. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 337–351 (1997)     

The suffix binary search tree and suffix AVL tree

Suffix trees and suffix arrays are classical data structures that are used to represent the set of suffixes of a given string, and thereby facilitate the efficient solution of various string processing problems—in particular on-line string searching. Here we investigate the potential of suitably adapted binary search trees as competitors in this context. The suffix binary search tree (SBST) and its balanced counterpart, the suffix AVL-tree, are conceptually simple, relatively easy to implement, and offer time and space efficiency to rival suffix trees and suffix arrays, with distinct advantages in some circumstances—for instance in cases where only a subset of the suffixes need be represented.

Construction of a suffix BST for an n-long string can be achieved in O(nh) time, where h is the height of the tree. In the case of a suffix AVL-tree this will be O(nlogn) in the worst case. Searching for an m-long substring requires O(m+l) time, where l is the length of the search path. In the suffix AVL-tree this is O(m+logn) in the worst case. The space requirements are linear in n, generally intermediate between those for a suffix tree and a suffix array.

Empirical evidence, illustrating the competitiveness of suffix BSTs, is presented.     

Proof of a conjecture of Fiedler and Markham

Let A be an n×n nonsingular M-matrix. For the Hadamard product AA⁻¹, M. Fiedler and T.L. Markham conjectured in [Linear Algebra Appl. 10l (1988) 1] that q(AA⁻¹)2/n, where q(AA⁻¹) is the smallest eigenvalue (in modulus) of AA⁻¹. We considered this conjecture in [Linear Algebra Appl. 288 (1999) 259] having observed an incorrect proof in [Linear Algebra Appl. 144 (1991) 171] and obtained that q(AA⁻¹)(2/n)(n−1)/n. The present paper gives a proof for this conjecture.     

On the complexity of searching game trees and other recursion trees

Game tree searching is one of the fundamental topics in artificial intelligence and decision analysis. The main results of this paper are: (1) A simple nondirectional algorithm for searching binary bi-valued game trees is presented and analysed. For a wide range of parameters s in Schrüfers s-tree model it has a smaller branching factor than directional search. (2) A cascade technique for game tree models with at least four different node values is presented. This technique yields algorithms with smaller branching factors than alpha-beta. (The amount of storage required by the algorithms in (1) and (2) is only linear in the depth of the searched trees.) (3) Recursion trees are defined as a natural generalisation of game trees. A combinatorial lower bound for the complexity of searching symmetric recursion trees is proved. (4) Those recursion trees are characterized which can be searched by pruning techniques.     

Limit laws for the Randić index of random binary tree models

We investigate the Randić index of random binary trees under two standard probability models: the one induced by random permutations and the Catalan (uniform). In both cases the mean and variance are computed by recurrence methods and shown to be asymptotically linear in the size of the tree. The recursive nature of binary search trees lends itself in a natural way to application of the contraction method, by which a limit distribution (for a suitably normalized version of the index) is shown to be Gaussian. The Randić index (suitably normalized) is also shown to be normally distributed in binary Catalan trees, but the methodology we use for this derivation is singularity analysis of formal generating functions.     

ContributionsSign-balanced covering matrices

A q × n array with entries from 0, 1,…,q − 1 is said to form a difference matrix if the vector difference (modulo q) of each pair of columns consists of a permutation of [0, 1,… q − 1]; this definition is inverted from the more standard one to be found, e.g., in Colbourn and de Launey (1996). The following idea generalizes this notion: Given an appropriate δ (-[−1, 1]^t, a λq × n array will be said to form a (t, q, λ, Δ) sign-balanced matrix if for each choice C₁, C₂,…, C_t of t columns and for each choice = (₁,…,_t) Δ of signs, the linear combination ∑_j=1^t _jC_j contains (mod q) each entry of [0, 1,…, q − 1] exactly λ times. We consider the following extremal problem in this paper: How large does the number k = k(n, t, q, λ, δ) of rows have to be so that for each choice of t columns and for each choice (₁, …, _t) of signs in δ, the linear combination ∑_j=1^t _jC_j contains each entry of [0, 1,…, q t- 1] at least λ times? We use probabilistic methods, in particular the Lovász local lemma and the Stein-Chen method of Poisson approximation to obtain general (logarithmic) upper bounds on the numbers k(n, t, q, λ, δ), and to provide Poisson approximations for the probability distribution of the number W of deficient sets of t columns, given a random array. It is proved, in addition, that arithmetic modulo q yields the smallest array - in a sense to be described.     

Representation complexity of adaptive 3D distance fields

In this paper we study the representation complexity of a kind of data structure that stores the information necessary to compute the distance from a point to a geometric body. These data structures called adaptive splitting based on cubature distance fields (ASBCDF), are binary search trees generated by the adaptive splitting based on cubature (ASBC) algorithm that adaptively subdivides the space surrounding the body into tetrahedra. Their representation complexity is measured by the number of nodes in the tree (two times the number of tetrahedra in the resulting tessellation). In the case of convex polyhedra we prove that this quantity remains bounded as the number of vertices of the polyhedra increases to infinity. Experimental results show that the number of tetrahedra in the tessellations is almost independent of the combinatorial complexity of the polyhedra. This means that the average compute time of the distance to arbitrary convex polyhedra is almost constant. Therefore, ASBCDFs are especially suitable for real time applications involving rapidly changing environments modelized with complex polyhedra.     

Average number of rotations and access cost in iR-trees

iR trees are parameterized binary search trees which rebalance themselves locally. In our previous work the cases fori=1, 2 were studied. This note extends the result to arbitraryi. In particular, we derive a formula for the average number of rotations/reorganizations involved in an insertion and consequently a formula for the average number of comparisons for a successful search iniR trees.     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

Cryptanalysis of Rijndael S-box and improvement

By the discovered correlation between linear functions over GF(qⁿ) and matrices over GF(q), a new scheme is presented to resolve the algebraic expression of Rijndael S-box in this paper. This new scheme has the advantage of predetermining in the case of a given random basis over GF(qⁿ). The reason why only nine terms are involved in the algebraic expression of Rijndael S-box is presented, which corrects the available inaccurate illustration. An improved AES S-box is presented to improve the complexity of AES S-box algebraic expression with terms increasing from 9 to 255 and algebraic degree invariable. The improved AES S-box also has good properties of Boolean functions in SAC and balance, and is capable of attacking against differential cryptanalysis with high reliable security. We finally summarize all the available methods to determine the algebraic expression of Rijndael S-box.     

Twist–Rotation Transformations of Binary Trees and Arithmetic Expressions

The paper studies the computational complexity and efficient algorithms for the twist–rotation transformations of binary trees, which is equivalent to the transformation of arithmetic expressions over an associative and commutative binary operation. The main results are (1) a full binary tree with n labeled leaves can be transformed into any other in at most 3n log n + 2n twist and rotation operations, (2) deciding the twist–rotation distance between two binary trees is NP-complete, and (3) the twist–rotation transformation can be approximated with ratio 6 log n + 4 in polynomial time for full binary trees with n uniquely labeled leaves.     

Iterative patching and the asymmetric traveling salesman problem

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover, Gutin, Yeo and Zverovich (2001) and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.     

Efficient Energy-preserving Methods for General Nonlinear Oscillatory Hamiltonian System

In this paper, we propose and analyze two kinds of novel and symmetric energy-preserving formulae for the nonlinear oscillatory Hamiltonian system of second-order differential equations Aq"(t)+ Bq(t)=f(q(t)), where A ∈ R^m×m is a symmetric positive definite matrix, B ∈ R^m×m is a symmetric positive semi-definite matrix that implicitly contains the main frequencies of the problem and f(q)=-▽_qV(q) for a real-valued function V(q). The energy-preserving formulae can exactly preserve the Hamiltonian H(q', q)=(1)/2q'^τ Aq' + (1)/2q^τ Bq + V(q). We analyze the properties of energy-preserving and convergence of the derived energy-preserving formula and obtain new efficient energy-preserving integrators for practical computation. Numerical experiments are carried out to show the efficiency of the new methods by the nonlinear Hamiltonian systems.     

On binary search tree recursions with monomials as toll functions

We consider distributional recursions which appear in the study of random binary search trees with monomials as toll functions. This extends classical parameters as the internal path length in binary search trees. As our main results we derive asymptotic expansions for the moments of the random variables under consideration as well as limit laws and properties of the densities of the limit distributions. The analysis is based on the contraction method.     

Maximal partial spreads and the modular n-queen problem

We prove that for any integer n in the interval there is a maximal partial spread of size n in PG (3, q) where q is odd and q7. We also prove that there are maximal partial spreads of size (q²+3)/2 when gcd(q+1,24)=2 or 4 and of size (q²+5)/2 when gcd(q+1,24)=4.     

Cubic theta functions

Some new identities for the four cubic theta functions a′(q,z), a(q,z), b(q,z) and c(q,z) are given. For example, we show that

a′(q,z)³=b(q,z)³+c(q)²c(q,z).

This is a counterpart of the identity

a(q,z)³=b(q)²b(q,z³)+c(q,z)³,

which was found by Hirschhorn et al.

The Laurent series expansions of the four cubic theta functions are given. Their transformation properties are established using an elementary approach due to K. Venkatachaliengar. By applying the modular transformation to the identities given by Hirschhorn et al., several new identities in which a′(q,z) plays the role of a(q,z) are obtained.