In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by $$\frac{4^{2\beta -\alpha }log\left(\alpha \right)(2\beta -1)(\alpha +1)(\alpha +2)\left(\genfrac{}{}{0pt}{}{2\alpha +1}{\alpha -1}\right)}{8\sqrt{\pi }{\alpha }^{3/2}log\left(2\right)(\beta -1)\beta {\left(\genfrac{}{}{0pt}{}{2\beta }{\beta }\right)}^2}$$ provided that α...

Given a graph with colored edges, a Hamiltonian cycle is called alternating if its successive edges differ in color. The problem of finding such a cycle, even for 2-edge-colored graphs, is trivially NP-complete, while it is known to be polynomial for 2-edge-colored complete graphs. In this paper we study the parallel complexity of finding such a cycle, if any, in 2-edge-colored complete graphs. We give a new characterization for such a graph admitting an alternating Hamiltonian cycle which allows...

In the job shop scheduling problem $k$-units-$J_m$, there are $m$ machines and each machine has an integer processing time of at most $k$ time units. Each job consists of a permutation of $m$ tasks corresponding to all machines and thus all jobs have an identical dilation $D$. The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed $k$, the makespan of an optimal schedule is at most $D+o\left(D\right)$, which extends the result of [3] for $k=1$; (ii) a randomized on-line approximation algorithm for $k$-units-...

In the job shop scheduling problem k-units-Jm, there are m machines and each machine has an integer processing time of at most k time units. Each job consists of a permutation of m tasks corresponding to all machines and thus all jobs have an identical dilation D. The contribution of this paper are the following results; (i) for $d=o\left(\sqrt{D}\right)$ jobs and every fixed k, the makespan of an optimal schedule is at most D+ o(D), which extends the result of [3] for k=1; (ii) a randomized on-line approximation...

This paper studies the computational complexity of the proper interval colored graph problem (PICG), when the input graph is a colored caterpillar, parameterized by hair length. In order prove our result we establish a close relationship between the PICG and a graph layout problem the proper colored layout problem (PCLP). We show a dichotomy: the PICG and the PCLP are NP-complete for colored caterpillars of hair length ≥2, while both problems are in P for colored caterpillars of hair length <2. For...

For p ≤ n, let b1(n),...,bp(n) be independent random vectors in ${ℝ}^n$ with the same distribution invariant by rotation and without mass at the origin. Almost surely these vectors form a basis for the Euclidean lattice they generate. The topic of this paper is the property of reduction of this random basis in the sense of Lenstra-Lenstra-Lovász (LLL). If ${\widehat{b}}_1^{\left(n\right)},...,{\widehat{b}}_p^{\left(n\right)}$ is the basis obtained from b1(n),...,bp(n) by Gram-Schmidt orthogonalization, the quality of the reduction depends upon the sequence of ratios...

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural assumptions...

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, i.e., the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under some natural...