Search

International audience; Semantic Backpropagation (SB) was introduced in GP so as to take into account the semantics of a GP tree at all intermediate states of the program execution, i.e., at each node of the tree. The idea is to compute the optimal " should-be " values each subtree should return, whilst assuming that the rest of the tree is unchanged, and to choose a subtree that matches as well as possible these target values. A single tree is evolved by iteratively replacing one of its nodes with the best subtree from a static library according to this local fitness, with tree size as a secondary criterion. Previous results for standard Boolean GP benchmarks that have been obtained by the authors with another variant of SB are improved in term of tree size. SB is then applied for the first time to categorical GP benchmarks, and outperforms all known results to date for three variable finite algebras.

We consider a problem of cost-constrained minimum-delay multicasting in a network, which is to find a Steiner tree spanning the source and destination nodes such that the maximum total delay along a path from the source node to a destination node is minimized, while the sum of link costs in the tree is bounded by a constant. The problem is $\mathcal{NP}$-hard even if the network is series-parallel. We present a fully polynomial time approximation scheme for the problem if the network is series-parallel.

The Priority Search Tree is the classic solution for the problem of dynamic 2-dimensional searching for the orthogonal query range of the form [a,b]×(-∞,c] (3-sided rectangle). It supports all operations in logarithmic worst case complexity in both main and external memory. In this work we show that the update and query complexities can be improved to expected doubly-logarithmic, when the input coordinates are being continuously drawn from specific probability distributions. We present three pairs of linear space solutions for the problem, i.e. a RAM and a corresponding I/O model variant: (1) First, we improve the update complexity to doubly-logarithmic expected with high probability, under the most general assumption that both the x- and y-coordinates of the input points are continuously being drawn from a distribution whose density function is unknown but fixed. (2) Next, we improve both the query complexity to doubly-logarithmic expected with high probability and the update complexity to doubly-logarithmic amortized expected, by assuming that only the x-coordinates are being drawn from a class of smooth distributions, and that the deleted points are selected uniformly at random among the currently stored points. In fact, the y-coordinates are allowed to be arbitrarily distributed. (3) Finally, we improve both the query and the update complexity to doubly-logarithmic expected with high probability by moreover assuming the y-coordinates to be continuously drawn from a more restricted class of realistic distributions. All data structures are deterministic and their complexity's expectation is with respect to the assumed distributions. They comprise combinations of known data structures and of two new data structures introduced here, namely the Weight Balanced Exponential Tree and the External Modified Priority Search Tree.

In the PEDAP algorithm, a minimum spanning tree considering the energy consumption is established based on the Kruskal algorithm, and updated every 100 rounds. There exists a defect that the energy of some nodes rapidly expires because the degrees of nodes differ significantly, and the delay time is not considered. Based on the above analysis, a new algorithm called DADAT (a Degree-based Adaptive algorithm for Data Aggregation Tree) is proposed. The energy consumption and the delay time are both considered, and a weight model to construct a minimum spanning tree is established. Furthermore, the node degree on the tree is readjusted according to the average degree of the network, and nodes are labeled by red, yellow, and green colors according to their remaining energy; the child nodes of the red nodes are adaptively transferred to their neighbor nodes which are labeled as green. Finally, we discuss the weight and the update rounds' impact on the network lifetime. Experimental results show that the algorithm can effectively balance the energy consumption and prolong the lifetime of the network, as well as achieving a lower latency.

Between the leaves and the nodes of a complete binary tree, a separate parent-child-sister hierarchy is employed independent of the parent-child-sister hierarchy used for the rest of the tree. Two different versions of such a local hierarchy are introduced. The result of the first proposed hierarchy is a faster and smaller footprint, while the second one provides the size variation functionality without a significant computational overhead. This novel approach brings considerable memory gains and performance boosts to the complete binary tree based algorithms., 12 pages research paper, contains 6 figures and a table

A ring tree is a tree graph with an optional additional edge that closes a unique cycle. Such a cycle is called a ring and the nodes on it are called ring nodes. The capacitated ring tree problem (CRTP) asks for a network of minimal overall edge cost that connects given customers to a depot by ring trees. Ring trees are required to intersect in the depot which has to be either a ring node of degree two in a ring tree or a node of degree one if the ring tree does not contain a ring. Customers are predefined as of type 1 or type 2. The type 2 customers have to be ring nodes, whereas type 1 customers can be either ring nodes or nodes in tree sub-structures. Additionally, optional Steiner nodes are given which can be used as intermediate network nodes if advantageous. Capacity constraints bound both the number of the ring trees as well as the number of customers allowed in each ring tree. In this paper we present first advanced neighborhood structures for the CRTP. Some of them generalize existing concepts for the TSP and the Steiner tree problem, others are CRTP-specific. We also describe models to explore these multinode and multi-edge exchange neighborhoods in one or more ring trees efficiently. Moreover, we embed these techniques in a heuristic multi-start framework and show that it produces high quality results for small and medium size literature instances.

International audience; The cubical dimension of a graph G is the smallest dimension of a hypercube into which G is embeddable as a subgraph. The conjecture of Havel [On hamiltonian circuits and spanning trees of hypercubes. ˇ Casopis ˇ Pest. Mat 109 (2) (1984) 135-152] claims that the cubical dimension of every balanced binary tree with 2n vertices, n 1, is n. The 2-rooted complete binary tree of depth n is obtained from two copies of the complete binary tree of depth n by adding an edge linking their respective roots. In this paper, we determine the cubical dimen- sion of trees obtained by subdividing twice a 2-rooted complete binary tree and prove that every such balanced tree satisfies the conjecture of Havel.

In this paper, we propose and analyze a simple localized algorithm to balance a tree. The motivation comes from live distributed streaming systems in which a source diffuses a content to peers via a tree, a node forwarding the data to its children. Such systems are subject to a high churn, peers frequently joining and leaving the system. It is thus crucial to be able to repair the diffusion tree to allow an efficient data distribution. In particular, due to bandwidth limitations, an efficient diffusion tree must ensure that node degrees are bounded. Moreover, to minimize the delay of the streaming, the depth of the diffusion tree must also be controlled. We propose here a simple distributed repair algorithm in which each node carries out local operations based on its degree and on the subtree sizes of its children. In a synchronous setting, we first prove that starting from any n-node tree our process converges to a balanced tree in O(n2) turns. We then describe a more restrictive model, adding a small extra information to each node, for which the convergence is reached in O(n log n) turns and this bound is tight. We then exhibit by simulation that the convergence is much faster (logarithmic number of turns in average) for a random tree.; Dans cet article, nous proposons et analysons un algorithme local simple pour ́equilibrer un arbre. La motivation vient des syst'emes distribu ́es de diffusion en temps r ́eel, dans lesquels une source diffuse un contenu vers des r ́ecepteurs via un arbre, un noeud transmettant les donn ́ees 'a ses enfants. Ces syst'emes sont soumis 'a un niveau ́elev ́e d'arriv ́ees et de d ́eparts (churn). Il est donc crucial d'ˆetre en mesure de r ́eparer efficacement l'arbre de diffusion afin de permettre une distribution efficace des donn ́ees. En particulier, en raison de limitations de bande passante, un arbre de diffusion efficace doit veiller 'a ce que les degr ́es des noeuds soient born ́es. Par ailleurs, pour minimiser le d ́elai de la diffusion en continu, la profondeur de l'arbre de diffusion doit ́egalement ˆetre contrˆol ́ee. Nous proposons ici un algorithme de r ́eparation distribu ́e simple dans lequel chaque nœud ex ́ecute des op ́erations locales en fonction de son degr ́e et de la taille des sous-arbres de ses enfants. Dans un cadre synchrone, nous montrons tout d'abord, qu''a partir de n'importe quel arbre avec n nœuds, notre processus converge vers un arbre ́equilibr ́e en O(n2) tours. Nous d ́ecrivons ensuite un mod'ele plus restrictif, en ajoutant une petite information suppl ́ementaire pour chaque nœud, pour lequel la convergence est atteinte en O(n log n) tours, cette borne ́etant serr ́ee. Nous mettons ensuite en ́evidence par simulation que la con- vergence est beaucoup plus rapide (nombre logarithmique de tours en moyenne) pour un arbre al ́eatoire.

In the classical (min-cost) Steiner tree problem, we are given an edge-weighted undirected graph and a set of terminal nodes. The goal is to compute a min-cost tree S which spans all terminals. In this paper we consider the min-power version of the problem (a.k.a. symmetric multicast), which is better suited for wireless applications. Here, the goal is to minimize the total power consumption of nodes, where the power of a node v is the maximum cost of any edge of S incident to v. Intuitively, nodes are antennas (part of which are terminals that we need to connect) and edge costs define the power to connect their endpoints via bidirectional links (so as to support protocols with ack messages). Observe that we do not require that edge costs reflect Euclidean distances between nodes: this way we can model obstacles, limited transmitting power, non-omnidirectional antennas etc. Differently from its min-cost counterpart, min-power Steiner tree is NP-hard even in the spanning tree case (a.k.a. symmetric connectivity), i.e. when all nodes are terminals. Since the power of any tree is within once and twice its cost, computing a ρst≤ln (4)+e [Byrka et al.'10] approximate min-cost Steiner tree provides a 2ρst

International audience; In this paper, we propose a new construction of constantdegree expanders motivated by their application in P2P overlay networks and in particular in the design of robust trees overlay. Our key result can be stated as follows. Consider a complete binary tree T and construct a random pairing Π between leaf nodes and internal nodes. We prove that the graph GΠ obtained from T by contracting all pairs (leaf-internal nodes) achieves a constant node expansion with high probability. The use of our result in improving the robustness of tree overlays is straightforward. That is, if each physical node participating to the overlay manages a random pair that couples one virtual internal node and one virtual leaf node then the physical-node layer exhibits a constant expansion with high probability. We encompass the difficulty of obtaining this random tree virtualization by proposing a local, selforganizing and churn resilient uniformly-random pairing algorithm with O(log2 n) running time. Our algorithm has the merit to not modify the original tree virtual overlay (we just control the mapping between physical nodes and virtual nodes). Therefore, our scheme is general and can be applied to a large number of tree overlay implementations. We validate its performances in dynamic environments via extensive simulations.

International audience; This paper revisits the tree constraint introduced in [2] which partitions the nodes of a n-nodes, m-arcs directed graph into a set of node-disjoint anti-arborescences for which only certain nodes can be tree roots. We introduce a new filtering algorithm that enforces generalized arc-consistency in O(n + m) time while the original filtering algorithm reaches O(nm) time. This result allows to tackle larger scale problems involving graph partitioning.

The problem of learning tree-structured Gaussian graphical models from independent and identically distributed (i.i.d.) samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that the extremal tree structure that minimizes the error exponent is the star for any fixed set of correlation coefficients on the edges of the tree. If the magnitudes of all the correlation coefficients are less than 0.63, it is also shown that the tree structure that maximizes the error exponent is the Markov chain. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime., Comment: Submitted to Transactions on Signal Processing

For random trees T generated by the binary search tree algorithm from uniformly distributed input we consider the subtree size profile, which maps k ∈ ℕ to the number of nodes in T that root a subtree of size k. Complementing earlier work by Devroye, by Feng, Mahmoud and Panholzer, and by Fuchs, we obtain results for the range of small k-values and the range of k-values proportional to the size n of T. In both cases emphasis is on the process view, i.e., the joint distributions for several k-values. We also show that the dynamics of the tree sequence lead to a qualitative difference between the asymptotic behaviour of the lower and the upper end of the profile.

The problem of learning tree-structured Gaussian graphical models from i.i.d. samples is considered. The influence of the tree structure and the parameters of the Gaussian distribution on the learning rate as the number of samples increases is discussed. Specifically, the error exponent corresponding to the event that the estimated tree structure differs from the actual unknown tree structure of the distribution is analyzed. Finding the error exponent reduces to a least-squares problem in the very noisy learning regime. In this regime, it is shown that universally, the extremal tree structures which maximize and minimize the error exponent are the star and the Markov chain for any fixed set of correlation coefficients on the edges of the tree. In other words, the star and the chain graphs represent the hardest and the easiest structures to learn in the class of tree-structured Gaussian graphical models. This result can also be intuitively explained by correlation decay: pairs of nodes which are far apart, in terms of graph distance, are unlikely to be mistaken as edges by the maximum-likelihood estimator in the asymptotic regime.

International audience; A binary unordered tree is a tree where each internal node has two children and the relative order of the subtrees of a node is not important (i.e. two trees are different if they differ only in the respective ordering of subtrees of nodes). We present a new method to generate all binary rooted unordered trees with n internal nodes, without duplications, in O(log n) time.

Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related results. A common idea used by all the algorithms for the problem is that a solution for complete binary trees is straightforward. Furthermore, for complete binary trees we can easily solve the problem in a distributed way by labeling the nodes of the tree such that from the labels of two nodes alone one can compute the label of their nearest common ancestor. Whether it is possible to distribute the data structure into short labels associated with the nodes is important for several applications such as routing. Therefore, related labeling problems have received a lot of attention recently.Previous optimal algorithms for nearest common ancestor queries work using some mapping from a general tree to a complete binary tree. However, it is not clear how to distribute the data structures obtained using these mappings. We conclude our survey with a new simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by our algorithm are of size $O(\log n)$ bits where $n$ is the number of nodes in the tree. The algorithm runs in $O(n)$ time.

In this paper we have studied fault tolerance of a full binary tree in terms of availability of non-faulty (full) subtrees. When an unaugmented full binary tree is faulty, then the computation can be carried out on the largest available non-faulty (full) binary subtree. It is shown that the minimum number of faulty nodes required to destroy all subtrees of height h in a full binary tree of height n is given as f bt ( n, h ) = ⌊ (2 n −1) (2 h −1) ⌋ . It follows that the availability of a non-faulty subtree of height h = n−w, in an n level full binary tree containing u faulty nodes, can be ensured, where w is the smallest integer such that u ≤ 2w. An algorithm which evaluates whether a given set of faulty nodes will destroy all subtrees of some specified height, is given. This algorithm can also evaluate the largest available non-faulty subtree in a faulty full binary tree. We also study the availability of a non-faulty subtree in some augmented binary tree architectures.

There is a way to define an average number of branches per vertex for an arbitrary infinite locally finite tree. It equals the exponential of the Hausdorff dimension of the boundary in an appropriate metric. Its importance for probabilistic processes on a tree is shown in several ways, including random walk and percolation, where it provides points of phase transition.

Given a sequence of numbers a l , …, a q , find a binary tree with q leaves minimizing max h l + a l , …, h q + a q , where h i is the distance from the i th leaf to the root, i = l , …, q . This problem is solved by means of a O( q ) algorithm and a tight upper bound for the minimum is given by an explicit formula. The task is equivalent to finding a binary tree of minimum height having q subtrees of heights a l , …, a q whose leaves partition the leaves of the tree. This question seems to be of general interest. In particular, it arises in the problem of the optimal decomposition of a tree into chains (Waksman, Tech. Report FC 95-06, August 1995).

In this paper, we study the static behavior of distributed memory architecture with general tree structures. After defining and discussing the notion of average diameter, we first show that the average time it takes to send messages between any two arbitrary processors in a binary tree structure with n processors is e(log n), through combinatorial analysis. We will also show that we can extend this result to general tree structures with n nodes, with a reasonable assumption, i.e., when m = o(n), where m is the maximum number of children any node could have. We believe that the results presented in this paper have captured some important inter-processor data transmission behavior of computers with distributed memory architectures, particularly those with (binary) tree structured inter-processor networks. As an application of combinatorial and a- symptotic analysis, this paper solves yet another average path length problem, thus is also theoreti- cally interesting. Finally, some of the techniques we have developed in this paper might also be useful in the study of similar problems. (~) 1998 Elsevier Science Ltd. All rights reserved.

It is shown that the complement of the tree with n nodes and exactly two adjacent non-endnodes, one of which is adjacent to exactly two endnodes, contains fewer cycles than the complement of any other tree with n nodes, provided n ⩾ 6.

We study the problem of minimizing the weighted average number of queries to identify an initially unknown object in a poset. We show that for general posets, there cannot be any o(logn)-approximation algorithm unless NP@?TIME(n^O^(^l^o^g^l^o^g^n^)). When the Hasse diagram of the partially ordered set has the structure of a tree, the problem is equivalent to the following tree search problem: in a given rooted tree T=(V,E) a node has been marked and we want to identify it. In order to locate the marked node, we can perform node queries. A node query u asks whether the marked node lies in the subtree rooted at u. A function w:V->Z^+ is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper the complexity of this problem had remained open. We prove that the above tree search problem is NP-complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 we show that the problem is polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP-complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O(|V|log|V|) time for trees with degree at most 2 (paths). Our results sharply contrast with those for the variant of the problem where one is interested in minimizing the maximum number of queries. In fact, for the worst case scenario, linear time algorithms are known for finding an optimal search strategy [K. Onak, P. Parys, Generalization of binary search: searching in trees and forest-like partial orders, in: FOCS'06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 2006, pp. 379-388; S. Mozes, K. Onak, O. Weimann, Finding an optimal tree searching strategy in linear time, in: SODA'08: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 1096-1105].

We show that binary search trees of a given size tend to have smaller height when the root division is into two subtrees of more balanced sizes. We deduce that the expectation of the absolute value of the difference in height of two binary search trees of the same number of nodes is less than 3.135 infinitely often. We also deduce strong upper bounds on the probability of large deviations from the median. Putting together these two conclusions and a simple and plausible conjecture on critical nodes leads to O(1) bounds on all moments of binary search tree heights.