Set to set broadcasting in communication networks

Suppose G = (V,E) is a graph whose vertices represent people and edges represent telephone lines between pairs of people. Each person knows a unique message and is ignorant of the messages of other people at the beginning. These messages are then spread by telephone calls. In each call, two people exchange all information they have so far in exactly one unit of time. Suppose A and B are two nonempty subsets of V. The main purpose of this paper is to study the minimum number b(A,B,G) of telephone calls by which A broadcasts to B; and the minimum time t(A,B,G) such that A broadcasts to B. In particular, we give an exact formula for b(A,B,K_n) and linear-time algorithms for computing b(A,B,T) and t(A,B,T) of a tree T.     

Phase diagram of the Ising Model on a Cayley tree in the presence of competing interactions and magnetic field

We study the phase diagram for the Ising Model on a Cayley tree with competing nearest-neighbor interactionsJ ₁ and next-nearest-neighbor interactionsJ ₂ andJ ₃ in the presence of an external magnetic field. To perform this study, an iterative scheme similar to that appearing in real space renormalization group frameworks is established; it recovers, as particular cases, previous works by Vannimenus and by Inawashiroet al. At vanishing temperature, the phase diagram is fully determined, for all values and signs ofJ ₂/J ₁ andJ ₃/J ₂; in particular, we verify that values ofJ ₃/J ₂ high enough favor the paramagnetic phase. At finite temperatures, several interesting features (evolution of reentrances, separation of the modulated region into two disconnected pieces, etc.) are exhibited for typical values ofJ ₂/J ₁ andJ ₃/J ₂.Partially supported by the Brazilian Agencies CNPq and FINEP.     

An improved partial SPIHT with classified weighted rate-distortion optimization for interferential multispectral image compression

Based on the property analysis of interferential multispectral images, a novel compression algorithm of partial set partitioning in hierarchical trees (SPIHT) with classified weighted rate-distortion optimization is presented.After wavelet decomposition, partial SPIHT is applied to each zero tree independently by adaptively selecting one of three coding modes according to the probability of the significant coefficients in each bitplane.Meanwhile the interferential multispectral image is partitioned into two kinds of regions in terms of luminous intensity, and the rate-distortion slopes of zero trees are then lifted with classified weights according to their distortion contribution to the constructed spectrum.Finally a global ratedistortion optimization truncation is performed.Compared with the conventional methods, the proposed algorithm not only improves the performance in spatial domain but also reduces the distortion in spectral domain.     

A lattice point problem on the regular tree

Huber (1956) [8] considered the following problem on the hyperbolic plane H. Consider a strictly hyperbolic subgroup of automorphisms on H with compact quotient, and choose a conjugacy class in this group. Count the number of vertices inside an increasing ball, which are images of a fixed point x∈H under automorphisms in the chosen conjugacy class, and describe the asymptotic behaviour of this number as the size of the ball goes to infinity. We use a well-known analogy between the hyperbolic plane and the regular tree to solve this problem on the regular tree.     

An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞[A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.     

Tangential Limits of Potentials on Homogeneous Trees

Let T be a homogeneous tree of homogeneity q+1. Let denote the boundary of T, consisting of all infinite geodesics b=[b ₀,b ₁,b ₂,] beginning at the root, 0. For each b, 1, and a0 we define the approach region _,a (b) to be the set of all vertices t such that, for some j, t is a descendant of b _j and the geodesic distance of t to b _j is at most (–1)j+a. If >1, we view these as tangential approach regions to b with degree of tangency . We consider potentials Gf on T for which the Riesz mass f satisfies the growth condition _T f ^p (t)q ^–|t|<, where p>1 and 0<<1, or p=1 and 0<1. For 11/, we show that Gf(s) has limit zero as s approaches a boundary point b within _,a (b) except for a subset E of of -dimensional Hausdorff measure 0, where H (E)=sup_>0inf _i q ^{–|t i|}:E a subset of the boundary points passing through t _i for some i,|t _i |>log _q (1/).     

A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem

In this paper, we present the design of a Polynomial Time Approximation Scheme (PTAS) for the Grade of Service Steiner Minimum Tree (GOSST) problem, which is known to be NP-Complete. Previous research has focused on geometric analyses and different approximation algorithms have been designed. We propose a PTAS that provides a polynomial time, near-optimal solution with performance ratio 1+. The GOSST problem has some important applications. In network design, a fundamental issue for the physical construction of a network structure is the interconnection of many communication sites with the best choice of the connecting lines and the best allocation of the transmission capacities over these lines. Good solutions should provide paths with enough communication capacities between any two sites, with the least network construction costs. Also, the GOSST problem has applications in transportation, for road constructions and some potential uses in CAD in terms of interconnecting the elements on a plane to provide enough flux between any two elements.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Algorithmic Aspects of Tree Amalgamation

The amalgamation of leaf-labeled trees into a single (super)tree that “displays” each of the input trees is an important problem in classification. We discuss various approaches to this problem and show that a simple and well-known polynomial-time algorithm can be used to solve this problem whenever the input set of trees contains a minimum size subset that uniquely determines the supertree. Our results exploit a recently established combinatorial property concerning the structure of such collections of trees.