Spanning caterpillars of a hypercube

Spanning trees of the hypercube Q_n have been recently studied by several authors. In this paper, we construct spanning trees of Q_n which are caterpillars and establish quantitative bounds for a caterpillar to span Q_n. As a corollary, we disprove a conjecture of Harary and Lewinter on the length of the spine of a caterpillar spanning Qⁿ. © 1997 John Wiley & Sons, Inc.     

Steiner minimal trees for three points with one convex polygonal obstacle

The problem of constructing Steiner minimal trees in the Euclidean plane is NP-hard. When in addition obstacles are present, difficulties of constructing obstacle-avoiding Steiner minimal trees are compounded. This problem, which has many obvious practical applications when designing complex transportation and distribution systems, has received very little attention in the literature. The construction of Steiner minimal trees for three terminal points in the Euclidean plane (without obstacles) has been completely solved (among others by Fermat, Torricelli, Cavallieri, Simpson, Heinen) during the span of the last three centuries. This construction is a cornerstone for both exact algorithms and heuristics for the Euclidean Steiner tree problem with arbitrarily many terminal points. An algorithm for three terminal points in the presence of one polygonal convex obstacle is given. It is shown that this algorithm has the worst-case time complexityO(n), wheren is the number of extreme points on the obstacle. As an extension to the underlying algorithm, if the obstacle is appropriately preprocessed inO(n) time, we can solve any problem instance with three arbitrary terminal points and the preprocessed convex polygonal obstacle inO(logn) time. We believe that the three terminal points algorithm will play a critical role in the development of heuristics for problem instances with arbitrarily many terminal points and obstacles.     

On the enumeration of certain sets of planted plane trees

Using the definition of planted plane trees given by D. A. Klarner (“A correspondence between sets of trees,” Indag. Math.31 (1969), 292–296) the number of nonisomorphic classes of certain sets of these trees is enumerated by obtaining a one-to-one correspondence between these classes and certain sets of nondecreasing vectors with integral components. A one-to-one correspondence between sets of (r + 1)-ary sequences and a certain set of planted plane trees is also established, which permits enumeration of this set. Finally, a natural generalization of Klarner's one-to-one correspondence between the above sets of trees and certain sets of edge-chromatic trees is obtained.     

Polygonizations of point sets in the plane

We examine the different ways a set ofn points in the plane can be connected to form a simple polygon. Such a connection is called apolygonization of the points. For some point sets the number of polygonizations is exponential in the number of points. For this reason we restrict our attention to star-shaped polygons whose kernels have nonempty interiors; these are callednondegenerate star-shaped polygons.We develop an algorithm and data structure for determining the nondegenerate star-shaped polygonizations of a set ofn points in the plane. We do this by first constructing an arrangement of line segments from the point set. The regions in the arrangement correspond to the kernels of the nondegenerate star-shaped polygons whose vertices are the originaln points. To obtain the data structure representing this arrangement, we show how to modify data structures for arrangements of lines in the plane. This data structure can be computed inO(n ⁴) time and space. By visiting the regions in this data structure in a carefully chosen order, we can compute the polygon associated with each region inO(n) time, yielding a total computation time ofO(n ⁵) to compute a complete list ofO(n ⁴) nondegenerate star-shaped polygonizations of the set ofn points.     

Successions in integer partitions

A partition of an integer n is a representation n=a ₁+a ₂+⋅⋅⋅+a _k , with integer parts 1≤a ₁≤a ₂≤…≤a _k . For any fixed positive integer p, a p-succession in a partition is defined to be a pair of adjacent parts such that a _i+1−a _i =p. We find generating functions for the number of partitions of n with no p-successions, as well as for the total number of such successions taken over all partitions of n. In the process, various interesting partition identities are derived. In addition, the Hardy-Ramanujan asymptotic formula for the number of partitions is used to obtain an asymptotic estimate for the average number of p-successions in the partitions of n. This material is based upon work supported by the National Research Foundation under grant number 2053740.     

On generalized independent subsets of trees

A natural generalization of the widely discussed independent (or “internally stable”) subsets of graphs is to consider subsets of vertices where no two elements have distance less or equal to a fixed number k (“k-independent subsets”). In this paper we give asymptotic results on the average number of ?-independent subsets for trees of size n, where the trees are taken from a so-called simply generated family. This covers a lot of interesting examples like binary trees, general planted plane trees, and others.     

Lucas' theorem refined ∗

We prove a refined version of the classical Lucas' theorem: if p is a polynomial with zeros a ₁,…,a _n+1 all having modulus one and φis the Blaschke product whose zeros are those of the derivative p ¹, then the compression of the shift S(φ) has its numerical range circumscribed about by the (n+ l)-gon a ₁…a _n+1 with tangent points the midpoints of then+ l sides of the polygon. This is proved via a special matrix representation of S(φ) and is a generalization of the known case for n= 2.     

Finding shortest paths in the plane in the presence of barriers to travel (for any lp - norm)

This paper develops an efficient algorithm for the computation of the shortest paths between given sets of points (origins and destinations) in the plane, when these paths are constrained not to cross any of a finite set of polygonal (open or closed) barriers. It is proved that when distances are measured by an 1_p - norm with 1 < p < ∞, these paths are formed by sequences straight line segments whose intermediate (e.g. apart from origin and destination) end points are barrier vertices. Moreover, only segments that locally support the barriers to which their end points belong are elligible for inclusion in a shortest path. The special case of one origin and one destination is considered, as well as the more general case of many origins and destinations. If n is the number of nodes (origins, destinations and barrier vertices), an algorithm is presented that builds that network of all shortest paths in O(n² log n) time. If the total number of edges in this network is e (bounded by n²), the application of Dijkstra's algorithm enables this computation of the shortest paths from any origin to all destinations in O(e log n) time. If the origins, shortest paths from all origins to all destinations can thus be found in O(ne log n) ≤ O(n^{3 log n}) time.It is also shown that optimal solutions when distances are measured according to the rectilinear or max-norm (i.e. l_p-norm with p = 1 or p = ∞) can be deduced from the results of the algorithm.     

Blocking Visibility for Points in General Position

For a finite set P in the plane, let b(P) be the smallest possible size of a set Q, Q∩P=∅, such that every segment with both endpoints in P contains at least one point of Q. We raise the problem of estimating b(n), the minimum of b(P) over all n-point sets P with no three points collinear. We review results providing bounds on b(n) and mention some additional observations.     

Trees with the seven smallest and eight greatest Harary indices

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. In this paper, we determined the first up to seventh smallest Harary indices of trees of order n≥16 and the first up to eighth greatest Harary indices of trees of order n≥14.     

The Inequality 8pg < μ for Hypersurface Two-dimensional Isolated Double Points

The Milnor number μ and the geometric genus p_g of normal 2-dimensional double points are studied by using Zariski's canonical resolution. By using formulas due to E. HORIKAWA and H. LAUFER, we represent μ ? 8p_g in terms of the number of blowing-ups along ?¹ and the number l of ?even”? components in the resolution process. A key point of our arguments is the fact that if l is small then the resolution process is restricted very much. For rational double points and double points with p_a = 1, each classes are characterized by numerical invariants appearing in this resolution process. For the case p_a = 1, we can make our inequality sharper and can prove 12 · p_g ? 3 ≤ μ. This is an another proof of Xu-Yau's inequality for the singularity with p_a = 1 in our situation.     

On the number of n-plexes

An n-plex of order p is an n-dimensional simplicial complex with p 0-simplexes in which every maximal simplex has dimension n or 0. An effective method is provided for calculating the number sⁿ_p of n-plexes of order p, and all values of sⁿ_p are computed for p≥9, thereby extending some results of Harary [1,2] and Oberschelp [5]. Connected n-plexes and self-complementary n-plexes are also enumerated and some useful asymptotic formulas are found.     

Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation

Summary. We study the role of preconditioning strategies recently developed for coercive problems in connection with a two-step iterative method, based on the Hermitian skew-Hermitian splitting (HSS) of the coefficient matrix, proposed by Bai, Golub and Ng for the solution of nonsymmetric linear systems whose real part is coercive. As a model problem we consider Finite Differences (FD) matrix sequences {A_n(a,p)}_n discretizing the elliptic (convection-diffusion) problem with being a plurirectangle of R^d with a(x) being a uniformly positive function and p(x) denoting the Reynolds function: here for plurirectangle we mean a connected union of rectangles in d dimensions with edges parallel to the axes. More precisely, in connection with preconditioned HSS/GMRES like methods, we consider the preconditioning sequence {P_n(a)}_n, P_n(a):= D_n^1/2(a)A_n(1,0) D_n^1/2(a) where D_n(a) is the suitably scaled main diagonal of A_n(a,0). If a(x) is positive and regular enough, then the preconditioned sequence shows a strong clustering at unity so that the sequence {P_n(a)}_n turns out to be a superlinear preconditioning sequence for {A_n(a,0)}_n where A_n(a,0) represents a good approximation of Re(A_n(a,p)) namely the real part of A_n(a,p). The computational interest is due to the fact that the preconditioned HSS method has a convergence behavior depending on the spectral properties of {P_n^-1(a)Re(A_n(a,p))}_n {P_n^-1(a)A_n(a,0)}_n: therefore the solution of a linear system with coefficient matrix A_n(a,p) is reduced to computations involving diagonals and to the use of fast Poisson solvers for {A_n(1,0)}_n.Some numerical experimentations confirm the optimality of the discussed proposal and its superiority with respect to existing techniques.Mathematics Subject Classification (1991): 65F10, 65N22, 15A18, 15A12, 47B65     

Large Quantile Estimation in a Multivariate Setting

An asymptotic theory is developed for the estimation of high quantile curves, i.e., sets of points in higher dimensional space for which the exeedance probability is p_n, with np_n → 0 (n → ∞). Here n is the number of available observations. This is the situation of interest if one wants to protect against a calamity that has not yet occurred. Asymptotic normality of the estimated quantile curve is proved under appropriate conditions, including the domain of the attraction condition for multivariate extremes.     

On plane trees with a prescribed number of valency set realizations

We describe valency sets of plane bicolored trees with a prescribed number of realizations by plane trees. Three special types of plane trees are defined: chains, trees of diameter 4, and special trees of diameter 6. We prove that there is a finite number of valency sets that have R realizations as plane trees and do not belong to these special types. The number of edges of such trees is less than or equal to 12R  + 2. The complete lists of valency sets of plane bicolored trees with 1, 2, or 3 realizations are presented. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 9–17, 2007.     

Analysis of three graph parameters for random trees

We consider three basic graph parameters, the node‐independence number, the path node‐covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size n asymptotically ～μn and ～νn, where the constants μ and ν depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Regularities in congruential random number generators

Summary This paper suggests, as did an earlier one, [1] that points inn-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established in [1] for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers—a symmetric, convex set of volume 2 ⁿ must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the coarse lattice structure of congruential generators. It gives a simple, self-contained proof that points inn-space produced by the general congruential generatorr _i+1 ar _i +b modm must fall on a lattice with unit-cell volume at leastm ^n–1 There is no restriction ona orb; this means thatall congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have ann-lattice with unit-cell volume 1.     

A transitive closure algorithm

An algorithm is given for computing the transitive closure of a directed graph in a time no greater thana ₁ N ₁ n+a ₂ n ² for largen wherea ₁ anda ₂ are constants depending on the computer used to execute the algorithm,n is the number of nodes in the graph andN ₁ is the number of arcs (not counting those arcs which are part of a cycle and not counting those arcs which can be removed without changing the transitive closure). For graphs where each arc is selected at random with probabilityp, the average time to compute the transitive closure is no greater than min{a ₁ pn ³+a ₂ n ², 1/2a ₁ n ² p ^–2+a ₂ n ²} for largen. The algorithm will compute the transitive closure of an undirected graph in a time no greater thana ₂ n ² for largen. The method uses aboutn ²+n bits and 5n words of storage (where each word can holdn+2 values).     

MAXIMUM TREES OF FINITE SEQUENCES

ＭＡＸＩＭＵＭＴＲＥＥＳＯＦＦＩＮＩＴＥＳＥＱＵＥＮＣＥＳ￥ＷＵＳＨＩＱＵＡＮＡｂｓｔｒａｃｔ：Ｌｅｔｎ，ｓ１，ｓ２，．．．，ｓｎｂｅｎｏｎ－ｎｅｇａｔｉｖｅｉｎｔｅｇｅｒｓａｎｄＭ（ｓ１，ｓ２，．．．，ｓｎ）＝｛（ａ１，ａ２，．．．，ａ．）｜ａｉｉ...     

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).