Virtual path layouts optimizing total hop count on ATM tree networks

This paper presents some algorithmic results concerning virtual path layouts for the one-to-many communication problem in ATM tree networks. The ATM network model is based on covering the network with a layout of virtual paths, under some constraints on the allowed load, namely, the number of paths that can share an edge. The quality measure used is the hop count, namely, the number of edges traversed between two vertices that need to communicate. Whereas most former results concerned the maximum hop count of the virtual path layout, our interest here is in measuring its total hop count, or alternatively its average hop count. The paper presents a dynamic programming algorithm for planning ATM network layouts with minimal total hop count for one-to-many requirements under load constraints over the class of tree networks.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

Constructions of new orthogonal arrays and covering arrays of strength three

A covering array of size N, strength t, degree k, and order v, or a CA(N;t,k,v) in short, is a k×N array on v symbols. In every t×N subarray, each t-tuple column vector occurs at least once. When ‘at least’ is replaced by ‘exactly’, this defines an orthogonal array, OA(t,k,v). A difference covering array, or a DCA(k,n;v), over an abelian group G of order v is a k×n array (aij) (1?i?k, 1?j?n) with entries from G, such that, for any two distinct rows l and h of D (1?l<h?k), the difference list Δlh={dh1−dl1,dh2−dl2,…,dhn−dln} contains every element of G at least once.Covering arrays have important applications in statistics and computer science, as well as in drug screening. In this paper, we present two constructive methods to obtain orthogonal arrays and covering arrays of strength 3 by using DCAs. As a consequence, it is proved that there are an OA(3,5,v) for any integer v?4 and v?2 (mod 4), and an OA(3,6,v) for any positive integer v satisfying gcd(v,4)≠2 and gcd(v,18)≠3. It is also proved that the size CAN(3,k,v) of a CA(N;3,k,v) cannot exceed v³+v² when k=5 and v≡2 (mod 4), or k=6, v≡2 (mod 4) and gcd(v,18)≠3.     

The mean uncertainty and distance dimension of multidimensional cantorian spaces

Several ways of describing the internal structure of infinite point sets and determining a corresponding average dimension are outlined. Possible relevance to discretisation of quantum space-time are discussed. Finally, a method for determining the average internal distance between different Cantor points is proposed.The main conclusion is that a micro-scale Cantorian space-time may be based on an average Cantorian distance d_l⁽⁰⁾ ⋍ 0.629, while the smooth space-time is retrieved when d_l⁽⁰⁾ → 0.5, which means d_l⁽⁰⁾ tends towards the average distance of a continuous smooth line at a vanishing resolution. This correspond to the case when space is viewed from very far, at the macro-scale of classical physics.     

The algebraic structure of the set of solutions to the Thue equation

Let Fn be a binary form with integral coefficients of degree n?2, let d denote the greatest common divisor of all non-zero coefficients of Fn, and let h?2 be an integer. We prove that if d=1 then the Thue equation (T) Fn(x,y)=h has relatively few solutions: if A is a subset of the set T(Fn,h) of all solutions to (T), with r:=card(A)?n+1, then

(#)

h divides the numberΔ(A):=_∏1?k<l?rδ(ξk,ξl),

where ξk=〈xk,yk〉∈A, 1?k?r, and δ(ξk,ξl)=xkyl−xlyk. As a corollary we obtain that if h is a prime number then, under weak assumptions on Fn, there is a partition of T(Fn,h) into at most n subsets maximal with respect to condition (#).     

What Is the Complexity of Surface Integration?

We study the worst case complexity of computing ε-approximations of surface integrals. This problem has two sources of partial information: the integrand f and the function g defining the surface. The problem is nonlinear in its dependence on g. Here, f is an r times continuously differentiable scalar function of l variables, and g is an s times continuously differentiable injective function of d variables with l components. We must have d⩽l and s⩾1 for surface integration to be well-defined. Surface integration is related to the classical integration problem for functions of d variables that are min{r, s−1} times continuously differentiable. This might suggest that the complexity of surface integration should be Θ((1/ε)^{d/min{r, s−1}}). Indeed, this holds when d<l and s=1, in which case the surface integration problem has infinite complexity. However, if d⩽l and s⩾2, we prove that the complexity of surface integration is O((1/ε)^d/min{r, s}). Furthermore, this bound is sharp whenever d<l.     

Routing-efficient CDS construction in Disk-Containment Graphs

In wireless networks, Connected Dominating Sets (CDSs) are widely used as virtual backbones for communications. On one hand, reducing the backbone size will reduce the maintenance overhead. So how to minimize the CDS size is a critical issue. On the other hand, when evaluating the performance of a wireless network, the hop distance between two communication nodes, which reflect the energy consumption and response delay, is of great importance. Hence how to minimize the routing cost is also a key problem for constructing the network virtual backbone. In this paper, we study the problem of constructing applicable CDS in wireless networks in terms of size and routing cost. We formulate a wireless network as a Disk-Containment Graph (DCG), which is a generalization of the Unit-Disk Graph (UDG), and we develop an efficient algorithm to construct CDS in such kind of graphs. The algorithm contains two parts and is flexible to balance the performance between the two metrics. We also analyze the algorithm theoretically. It is shown that our algorithm has provable performance in minimizing the CDS size and reducing the communication distance for routing.     

Local and global norm comparison theorems for solutions to the nonhomogeneous A-harmonic equation

We establish local and global norm inequalities for solutions of the nonhomogeneous A-harmonic equation A(x,g+du)=h+d^?v for differential forms. As applications of these inequalities, we prove the Sobolev-Poincaré type imbedding theorems and obtain Lp-estimates for the gradient operator ∇ and the homotopy operator T from the Banach space Ls(D,Λl) to the Sobolev space W1,s(D,Λl−1), l=1,2,…,n. These results can be used to study both qualitative and quantitative properties of solutions of the A-harmonic equations and the related differential systems.     

Maximizing a lower bound on the computational complexity

We solve a combinatorial problem that arises in determining by a method due to Engeler lower bounds for the computational complexity of algorithmic problems. Denote by G_d the class of permutation groups G of degree d that are iterated wreath products of symmetric groups, i.e. G = S_dh?11?1S_d0 with Π^h?1_i=0d_i = d for some natural number h and some sequence (d₀,…,d_h?1) of natural numbers greater than 1. The problem is to characterize those G = S_dh?11?1S_d0 in G_d on which k(G):=log|G|/max_0≤i≤h?1log(d_i!) assumes its maximum. Our solution consists of two necessary conditions for this, namely that d₀≤d₁≤?≤d_h and that d_h is the largest prime divisor of d. Consequently, if d is a prime power, say d = p^h with p prime, then a necessary and sufficient condition is that d_i = p, 0 ≤ i ≤ h ? 1.     

A geometric approach to Mathon maximal arcs

In 1969 Denniston [3] gave a construction of maximal arcs of degree d in Desarguesian projective planes of even order q, for all d dividing q. In 2002 Mathon [8] gave a construction method generalizing the one of Denniston. We will give a new geometric approach to these maximal arcs. This will allow us to count the number of isomorphism classes of Mathon maximal arcs of degree 8 in PG(2,h²), h prime.     

On non-antipodal binary completely regular codes

Binary non-antipodal completely regular codes are characterized. Using a result on nonexistence of nontrivial binary perfect codes, it is concluded that there are no unknown nontrivial non-antipodal completely regular binary codes with minimum distance d?3. The only such codes are halves and punctured halves of known binary perfect codes. Thus, new such codes with covering radius ρ=6 and 7 are obtained. In particular, a half of the binary Golay [23,12,7]-code is a new binary completely regular code with minimum distance d=8 and covering radius ρ=7. The punctured half of the Golay code is a new completely regular code with minimum distance d=7 and covering radius ρ=6. The new code with d=8 disproves the known conjecture of Neumaier, that the extended binary Golay [24,12,8]-code is the only binary completely regular code with d?8. Halves of binary perfect codes with Hamming parameters also provide an infinite family of binary completely regular codes with d=4 and ρ=3. Puncturing of these codes also provide an infinite family of binary completely regular codes with d=3 and ρ=2. Both these families of codes are well known, since they are uniformly packed in the narrow sense, or extended such codes. Some of these completely regular codes are new completely transitive codes.     

Pseudo-similar points in ordered sets

Two points l and h in an ordered set P are called pseudo-similar iff P?{l} is isomorphic to P?{h} and there is no automorphism of P that maps l to h. This paper provides a characterization of ordered sets with at least two pseudo-similar points. Special attention is given to ordered sets with pseudo-similar points l and h so that one of the points is minimal and the other is maximal. These sets will play a key role in the reconstruction of the rank of the removed element in a non-extremal card.     

Two-body threshold spectral analysis, the critical case

We study in dimension d?2 low-energy spectral and scattering asymptotics for two-body d-dimensional Schrödinger operators with a radially symmetric potential falling off like −γr−2, γ>0. We consider angular momentum sectors, labelled by l=0,1,…, for which γ>²(l+d/2−1). In each such sector the reduced Schrödinger operator has infinitely many negative eigenvalues accumulating at zero. We show that the resolvent has a non-trivial oscillatory behaviour as the spectral parameter approaches zero in cones bounded away from the negative half-axis, and we derive an asymptotic formula for the phase shift.     

Job shop scheduling with unit time operations under resource constraints and release dates

We consider the problem of job shop scheduling with m machines and n jobs J_i, each consisting of l_i unit time operations. There are s distinct resources R_h and a quantity q_h available of each one. The execution of the j-th operation of J_i requires the presence of u_ijh units of R_h, 1 ≤i≤n, 1 ≤j≤l_i, and 1 ≤h≤s. In addition, each J_i has a release date r_i, that is J_i cannot start before time r_i. We describe algorithms for finding schedules having minimum length or sum of completion times of the jobs. Let l=max{l_i} and u=|{u_ijh}|. If m, u and l are fixed, then both algorithms terminate within polynomial time.     

Class number one quadratic fields and solvability of some Pellian equations

Consider these two types of positive square-free integers d≠ 1 for which the class number h of the quadratic field Q(√d) is odd: (1) d is prime∈ 1(mod 8), or d=2q where q is prime ≡ 3 (mod 4), or d=qr where q and r are primes such that q≡ 3 (mod 8) and r≡ 7 (mod 8); (2) d is prime ≡ 1 (mod 8), or d=qr where q and r are primes such that q≡r≡ 3 or 7 (mod 8). For d of type (2) (resp. (1)), let Π be the set of all primes (resp. odd primes) p∈N satisfying (d/p) = 1. Also, let δ :=0 (resp. δ :=1) if d≡ 2,3 (mod 4) (resp. d≡ 1 (mod 4)). Then the following are equivalent: (a) h=1; (b) For every p∈П at least one of the two Pellian equations Z ²-dY ² = ±4^δ p is solvable in integers. (c) For every p∈П the Pellian equation W ²-dV ² = 4^δ p ² has a solution (w,v) in integers such that gcd (w,v) divides 2^δ.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Subexponential estimates in the height theorem and estimates on numbers of periodic parts of small periods

This paper is devoted to subexponential estimates in Shirshov’s height theorem. A word W is n-divisible if it can be represented in the form W = W ₀ W ₁ ?W _n , where W ₁ ? W ₂ ??? W _n . If an affine algebra A satisfies a polynomial identity of degree n, then A is spanned by non-n-divisible words of generators a ₁ ??? a _l . A. I. Shirshov proved that the set of non-n-divisible words over an alphabet of cardinality l has bounded height h over the set Y consisting of all words of degree ≤ n ? 1. We show that h < Φ (n, l), where Φ(n, l) = 2⁸⁷ l?n ^{12 log3 n+48}. Let l, n, and d ≥ n be positive integers. Then all words over an alphabet of cardinality l whose length is greater than ψ(n, d, l) are either n-divisible or contain the dth power of a subword, where ψ(n, d, l) = 2¹⁸ l(nd)^{3 log3(nd)+13} d ². In 1993, E. I. Zelmanov asked the following question in the Dniester Notebook: Suppose that F _2,m is a 2-generated associative ring with the identity x ^m = 0. Is it true that the nilpotency degree of F _2,m has exponential growth? We give the definitive answer to E. I. Zelmanov by this result. We show that the nilpotency degree of the l-generated associative algebra with the identity x ^d = 0 is smaller than ψ(d, d, l). This implies subexponential estimates on the nilpotency index of nil-algebras of arbitrary characteristic. Shirshov’s original estimate was just recursive; in 1982 a double exponent was obtained, and an exponential estimate was obtained in 1992. Our proof uses Latyshev’s idea of an application of the Dilworth theorem. We think that Shirshov’s height theorem is deeply connected to problems of modern combinatorics. In particular, this theorem is related to the Ramsey theory. We obtain lower and upper estimates of the number of periods of length 2, 3, n ? 1 in some non-n-divisible word. These estimates differ only by a constant.     

An explicit height bound for the classical modular polynomial

For a prime l, let Φ _l be the classical modular polynomial, and let h(Φ _l ) denote its logarithmic height. By specializing a theorem of Cohen, we prove that \(h(\Phi_{l})\le 6l\log l+16l+14\sqrt{l}\log l\). As a corollary, we find that h(Φ _l )≤6llog?l+18l also holds. A table of h(Φ _l ) values is provided for l≤3600.