The Variance of the height of binary search trees

By using analytic tools it is shown that the variance E(H_n−EH_n)² of the height H_n of binary search trees of size n is bounded.     

A limit characterization for the number of spanning trees of graphs

In this paper we propose a limit characterization of the behaviour of classes of graphs with respect to their number of spanning trees. Let {G_n} be a sequence of graphs G₀,G₁,G₂,… that belong to a particular class. We consider graphs of the form K_n−G_n that result from the complete graph K_n after removing a set of edges that span G_n. We study the spanning tree behaviour of the sequence {K_n−G_n} when n→∞ and the number of edges of G_n scales according to n. More specifically, we define the spanning tree indicator ({G_n}), a quantity that characterizes the spanning tree behaviour of {K_n−G_n}. We derive closed formulas for the spanning tree indicators for certain well-known classes of graphs. Finally, we demonstrate that the indicator can be used to compare the spanning tree behaviour of different classes of graphs (even when their members never happen to have the same number of edges).     

On some dynamical subsets of the rauzy fractal

Let ( ,(+1)_n) be the adic system associated to the substitution: 1 → 12,…,(n − 1) → 1n, n → 1. In Sirvent (1996) it was shown that there exist a subset Cⁿ of and a map h_n: C → Cⁿ such that the dynamical system (C, h_n) is semiconjugate to ( ). In this paper we compute the Hausdorff and Billingsley dimensions of the geometrical realizations of the set Cⁿ on the (n− l)-dimensional torus. We also show that the dynamical system (Cⁿ,h_n) cannot be realized on the (n − 1)-torus.     

Order-configuration functions: Mathematical characterizations and applications to digital signal and image processing

We call a function f in n variables an order-configuration function if for any x₁,…, x_n such that x_i1 … x_in we have f(x₁,…, x_n) = x_t, where t is determined by the n-tuple (i₁,…, i_n) corresponding to that ordering. Equivalently, it is a function built as a minimum of maxima, or a maximum of minima. Well-known examples are the minimum, the maximum, the median, and more generally rank functions, or the composition of rank functions. Such types of functions are often used in nonlinear processing of digital signals or images (for example in the median or separable median filter, min-max filters, rank filters, etc.). In this paper we study the mathematical properties of order-configuration functions and of a wider class of functions that we call order-subconfiguration functions. We give several characterization theorems for them. We show through various examples how our concepts can be used in the design of digital signal filters or image transformations based on order-configuration functions.     

A novel algorithm for fast computation of Zernike moments

Zernike moments (ZMs) have been successfully used in pattern recognition and image analysis due to their good properties of orthogonality and rotation invariance. However, their computation by a direct method is too expensive, which limits the application of ZMs. In this paper, we present a novel algorithm for fast computation of Zernike moments. By using the recursive property of Zernike polynomials, the inter-relationship of the Zernike moments can be established. As a result, the Zernike moment of order n with repetition m, Z_nm, can be expressed as a combination of Z_n−2,m and Z_n−4,m. Based on this relationship, the Zernike moment Z_nm, for n>m, can be deduced from Z_mm. To reduce the computational complexity, we adopt an algorithm known as systolic array for computing these latter moments. Using such a strategy, the multiplication number required in the moment calculation of Z_mm can be decreased significantly. Comparison with known methods shows that our algorithm is as accurate as the existing methods, but is more efficient.     

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Let V = v₁, v₂, …, v_m and W = w₁, w₂, …, w_n be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.     

A robustness measure for hypercube networks

Hypercube networks offer a feasible cost-effective solution to parallel computing. Here, a large number of low-cost processors with their own local memories are connected to form an n-cube (B_n) or one of its variants; and the inter-processor communication takes place by message passing instead of shared variables. This paper addresses a constrained two-terminal reliability measure referred to as distance reliability (DR) as it considers the probability that a message can be delivered in optimal time from a given node s to a node t. The problem is equivalent to that of having an operational optimal path (not just any path) between the two nodes. In B_n, the Hamming distance between labels of s and t or H(s, t) determines the length of the optimal path between the two nodes. The shortest distance restriction guarantees optimal communication delay between processors and high link/node utilization across the network. Moreover, it provides a measure for the robustness of symmetric networks. In particular, when H(s, t) = n in B_n, DR will yield the probability of degradation in the diameter, a concept which directly relates to fault-diameter. The paper proposes two schemes to evaluate DR in B_n. The first scheme uses a combinatorial approach by limiting the number of faulty components to (2H(s, t) − 2), while the second outlines paths of length H(s, t) and, then generates a recursive closed-form solution to compute DR. The theoretical results have been verified by simulation. The discrepancy between the theoretical and simulation results is in most cases below 1% and in the worst case 4.6%.     

Lyapunov exponents of the logistic map with periodic forcing

The iterative map x_n+1 = r_nx_n (1 - x_n) is investigated with r_n changing periodically between two values A and B. Different periodicities are assumed, e.g., {r_n} = {BABA …} or {r_n} = {BBABA BBABA …}. The Lyapunov exponent (a measure of average stability) is displayed with high resolution on the A-B-plane. The resulting images have aesthetically appealing self-similar structures. Furthermore, these images allow with one glimpse the identification of a number of system properties: coexistence of attractors, superstable curves, order by alternation of chaotic processes, and chaos by periodic resetting from a stable into an unstable fixed point.     

Computing multidimensional Delaunay tessellations

We recall some properties of Voronoi and Delaunay tessellations in any numbers of dimensions. We then propose a solution to the following problem: Given the Delaunay tessellation of n d-dimensional data points X₁,…, X_n, the proble is to insert a new data point X and to update the tessellation accordingly. The solution proposed achieves minimum space-complexity.     

Computational complexity of distributed detection problems with information constraints

For a system consisting of a set of sensors S = {S₁, S₂, …, S_m} and a set of objects O = {O₁, O₂, …, O_n}, there are information constraints given by a relation R S × O such that (S_i, O_j) R if and only if S_i is capable of detecting O_j. Each (S_i, O_j) R is assigned a confidence factor (a positive real number) which is either explicitly given or can be efficiently computed. Given that a subset of sensors have detected obstacles, the detection problem is to identify a subset H O with the maximum confidence value. The computational complexity of the detection problem, which depends on the nature of the confidence factor and the information constraints, is the main focus of this paper. This problem exhibits a myriad of complexity levels ranging from a worst-case exponential (in n) lower bound in a general case to an O(m + n) time solvability. We show that the following simple versions of a detection problem are computationally intractable: (a) deterministic formulation, where confidence factors are either 0 or 1; (b) uniform formulation where (S_i, O_j) R, for all S_i S, O_j O; (c) decomposable systems under multiplication operation. We then show that the following versions are solvable in polynomial (in n) time: (a) single object detection; (b) probabilistically independent detection; (c) decomposable systems under additive and nonfractional multiplicative measures; and (d) matroid systems.     

Similarity-based ranking and query processing in multimedia databases

Since media-based evaluation yields similarity values, results to a multimedia database query, Q(Y₁,…,Y_n), is defined as an ordered list S_Q of n-tuples of the form X₁,…,X_n. The query Q itself is composed of a set of fuzzy and crisp predicates, constants, variables, and conjunction, disjunction, and negation operators. Since many multimedia applications require partial matches, S_Q includes results which do not satisfy all predicates. Due to the ranking and partial match requirements, traditional query processing techniques do not apply to multimedia databases. In this paper, we first focus on the problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, providing the user with a meaningful final ranking”. More specifically, we study the problem of merging similarity values in queries with multiple fuzzy predicates. We describe the essential multimedia retrieval semantics, compare these with the known approaches, and propose a semantics which captures the requirements of multimedia retrieval problem. We then build on these results in answering the related problem of “given a multimedia query which consists of multiple fuzzy and crisp predicates, finding an efficient way to process the query.” We develop an algorithm to efficiently process queries with unordered fuzzy predicates (sub-queries). Although this algorithm can work with different fuzzy semantics, it benefits from the statistical properties of the semantics proposed in this paper. We also present experimental results for evaluating the proposed algorithm in terms of quality of results and search space reduction.     

Algorithm for converting a forest of quadtrees to a binary array

An algorithm for reconstructing a binary array of size N sx N from its forest of quadtree representation is presented. The algorithm traverses each tree of the forest in preorder and maps each ‘black’ node into the spatial domain. The time complexity in mapping is O(log N × B_n + B_p), where B_n is the number of black nodes in the forest and B_p is the number of black pixels in the N × N array. The algorithm has been implemented on an Apple II.     

Efficient enumeration of all minimal separators in a graph

This paper presents an efficient algorithm for enumerating all minimal a-b separators separating given non-adjacent vertices a and b in an undirected connected simple graph G = (V, E), Our algorithm requires O(n³R_ab) time, which improves the known result of O(n⁴R_ab) time for solving this problem, where ¦V¦= n and R_ab is the number of minimal a-b separators. The algorithm can be generalized for enumerating all minimal A-B separators that separate non-adjacent vertex sets A, B < V, and it requires O(n²(n − n_A − n_b)R_AB) time in this case, where n_a = ¦A¦, n_B = ¦B¦ and r_AB is the number of all minimal A−B separators. Using the algorithm above as a routine, an efficient algorithm for enumerating all minimal separators of G separating G into at least two connected components is constructed. The algorithm runs in time O(n³R⁺_Σ + n⁴R_Σ), which improves the known result of O(n⁶R_Σ) time, where R_σ is the number of all minimal separators of G and R_ΣR⁺_Σ = ∑_1i, v_j) ER_vivj n − 1)/2 − m)R_Σ. Efficient parallelization of these algorithms is also discussed. It is shown that the first algorithm requires at most O((n/log n)R_ab) time and the second one runs in time O((n/log n)R⁺_Σ+n log nR_Σ) on a CREW PRAM with O(n³) processors.     

Calculating polynomial zeros on a local memory parallel computer

We consider the calculation, on a local memory parallel computer, of all the zeros of an n th degree polynomial P_n(x) which has real coefficients. We describe a generic parallel algorith, which approximates all the zeros simultaneously and we give three specific examples of this algorithm which have orders of convergence two, three and four. We report extensive numerical tests of the algorithms; the fourth order algorithm is not robust, with many failures to convergence, whereas the other two algorithms are reliable and display very respectable parallel speedups for higher degree polynomials.     

Fault-Tolerant Hamiltonicity and Hamiltonian Connectivity of BCube with Various Faulty Elements

BCube is one kind of important data center networks. Hamiltonicity and Hamiltonian connectivity have significant applications in communication networks. So far, there have been many results concerning fault-tolerant Hamiltonicity and fault-tolerant Hamiltonian connectivity in some data center networks. However, these results only consider faulty edges and faulty servers. In this paper, we study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity of BCube(n, k) under considering faulty servers, faulty links/edges, and faulty switches. For any integers n ≥ 2 and k ≥ 0, let BC_n,k be the logic structure of BCube(n, k) and F be the union of faulty elements of BC_n,k. Let f_v, f_e, and f_s be the number of faulty servers, faulty edges, and faulty switches of BCube(n, k), respectively. We show that BC_n,k-F is fault-tolerant Hamiltonian if f_v + f_e + (n-1)f_s ≤ (n-1)(k + 1)-2 and BC_n,k-F is fault-tolerant Hamiltonian-connected if f_v + f_e + (n-1)f_s ≤ (n-1)(k + 1)-3. To the best of our knowledge, this paper is the first work which takes faulty switches into account to study the fault-tolerant Hamiltonicity and the fault-tolerant Hamiltonian connectivity in data center networks.     

A new way of counting n

In this paper, we shall give a combinatorial proof of the following equation:

,

where m and n are positive integers, m ≤ n, and k₁, k₂, …, k_n-1 are nonnegative integers.     

Simultaneous H control of a finite collection of linear plants with a single nonlinear digital controller

This paper considers the problem of simultaneous H^∞ control of a finite collection of linear time-invariant systems via a nonlinear digital output feedback controller. The main result is given in terms of the existence of suitable solutions to Riccati algebraic equations and a dynamic programming equation. Our main result shows that if the simultaneous H^∞ control problem for k linear time-invariant plants of orders n₁,n₂,…,n_k can be solved, then this problem can be solved via a nonlinear time-invariant controller of order nn₁+n₂++n_k.     

Subspace selection algorithms to be used with the nonlinear projection methods in solving systems of nonlinear equations

The nonlinear projection methods are minimization procedures for solving systems of nonlinear equations. They permit reevaluation of n_k, 1 ≤ n_k ≤ n, components of the approximate solution vector at each iteration step where n is the dimension of the system. At iteration step k, the reduction in the norm of the residue vector depends upon the n_k components which are reevaluated. These n_k components are obtained by solving a linear system.

We present two algorithms for determining the components to be modified at each iteration of the nonlinear projection method and compare the use of these algorithms to Newton's method. The computational examples demonstrate that Newton's method, which reevaluates all components of the approximate solution vector at each iteration, can be accelerated by using the projection techniques.     

Periodic solutions of a class of nonlinear difference equations via critical point method

In this paper, we obtain some new sufficient conditions for the existence of nontrivial m-periodic solutions of the following nonlinear difference equation

by using the critical point method, where f: Z × R → R is continuous in the second variable, m ≥ 2 is a given positive integer, p_n+m = p_n for any n  Z and f(t + m, z) = f(t, z) for any (t, z)  Z × R, (−1)^δ = −1 and δ > 0.     

Complexity of Boolean algebras

We show that the elementary theory of Boolean algebras is _log-complete for the Berman complexity class _c<ω STA(*, 2^cn, n), the class of sets accepted by alternating Turing machines running in time 2^cn for some constant c and making at most n alternations on inputs of length n; thus the theory is computationally equivalent to the theory of real addition with order. We extend the completeness results to various subclasses of Boolean algebras, including the finite, free, atomic, atomless, and complete Boolean algebras. Finally we show that the theory of any finite collection of finite Boolean algebras is complete for PSPACE, while the theory of any other collection is _log-hard for _c<ω STA(*, 2^cn, n).