1,720,976 research outputs found
On coding labeled trees
Full text linkTrees are probably the most studied class of graphs in Computer Science. In this thesis we study bijective codes that represent labeled trees by means of string of node labels. We contribute to the understanding of their algorithmic tractability, their properties, and their applications.
The thesis is divided into two parts. In the first part we focus on two types of tree codes, namely Prufer-like codes and Transformation codes. We study optimal encoding and decoding algorithms, both in a sequential and in a parallel setting. We propose a unified approach that works for all Prufer-like codes and a more generic scheme based on the transformation of a tree into a functional digraph suitable for all bijective codes. Our results in this area close a variety of open problems.
We also consider possible applications of tree encodings, discussing how to exploit these codes in Genetic Algorithms and in the generation of random trees. Moreover, we introduce a modified version of a known code that, in Genetic Algorithms, outperform all the other known codes.
In the second part of the thesis we focus on two possible generalizations of our work. We first take into account the classes of k-trees and k-arch graphs (both superclasses of trees): we study bijective codes for this classes of graphs and their algorithmic feasibility. Then, we shift our attention to Informative Labeling Schemes. In this context labels are no longer considered as simple unique node identifiers, they rather convey information useful to achieve efficient computations on the tree. We exploit this idea to design a concurrent data structure for the lowest common ancestor problem on dynamic trees.
We also present an experimental comparison between our labeling scheme and the one proposed by Peleg for static trees
On the number of labeled k-arch graphs
No full textIn this paper we deal with k-arch graphs, a superclass of trees and k-trees. We give a recursive function counting the number of labeled k-arch graphs. Our result relies on a generalization of the well-known Prüfer code for labeled trees. In order to guarantee the generalized code to be a bijection, we characterize the valid code strings. A previous attempt at counting the number of labeled k-arch graphs was made by Lamathe. We point out an error in his work, and prove it by giving a counterexample
Engineering Tree Labeling Schemes: a Case Study on Least Common Ancestor
No full textWe address the problem of labeling the nodes of a tree such that one can determine the identifier of the least common ancestor of any two nodes by looking only at their labels. This problem has application in routing and in distributed computing in peer-to-peer networks. A labeling scheme using Θ(log2 n)-bit labels has been previously presented by Peleg. By engineering this scheme, we obtain a variety of data structures with the same asymptotic performances. We conduct a thorough experimental evaluation of all these data structures. Our results clearly show which variants achieve the best performances in terms of space usage, construction time, and query time. © 2008 Springer-Verlag Berlin Heidelberg
Bijective Linear Time Coding and Decoding for k-Trees
No full textThe problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 R,nyi and R,nyi generalized the Prufer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or R,nyi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with respect to the size of the k-tree
String Coding of Trees with Locality and Heritability
No full textWe consider the problem of coding labelled trees by means of strings of vertex labels and we present a general scheme to define bijective codes based on the transformation of a tree into a functional digraph. Looking at the fields in which codes for labelled trees are utilized, we see that the properties of locality and heritability are required and that codes like the well known Prüfer code do not satisfy these properties. We present a general scheme for generating codes based on the construction of functional digraphs. We prove that using this scheme, locality and heritability are satisfied as a direct function of the similarity between the topology of the functional digraph and that of the original tree. Moreover, we also show that the efficiency of our method depends on the transformation of the tree into a functional digraph. Finally we show how it is possible to fit three known codes into our scheme, obtaining maximum efficiency and high locality and heritability
On coding labeled trees
No full textWe consider the problem of coding labeled trees by means of strings of node labels. Different codes have been introduced in the literature by Prufer, Neville, and Deo and Micikevicius. For all of them, we show that both coding and decoding can be reduced to integer (radix) sorting, closing several open problems within a unified framework that can be applied both in a sequential and in a parallel setting. Our sequential coding and decoding schemes require optimal O(n) time when applied to n-node trees, yielding the first linear time decoding algorithm for a code presented by Neville. These schemes can be parallelized on the EREW PRAM model. so as to work in O(log n) time with cost O(n), O(n root log n), or O(n log n), depending on the code and on the operation: in all cases, they either match or improve the performances of the best ad hoc approaches known so far. (c) 2007 Elsevier B.V. All rights reserved
A unified approach to coding labeled trees
No full textWe consider the problem of coding labeled trees by means of strings of node labels and we present a unified approach based on a reduction of both coding and decoding to integer (radix) sorting. Applying this approach to four well-known codes introduced by Prufer [18], Neville [17], and Deo and Micikevicius [5], we close some open problems. With respect to coding, our general sequential algorithm requires optimal linear time, thus solving the problem of optimally computing the second code presented by Neville. The algorithm can be parallelized on the EREW PRAM model, so as to work in O(log n) time using O(n) or O(nrootlog n) operations, depending on the code. With respect to decoding, the problem of finding an optimal sequential algorithm for the second Neville code was also open, and our general scheme solves it. Furthermore, in a parallel setting our scheme yields the first efficient decoding algorithms for the codes in [5] and [17]
Resilient Dynamic Programming
Full text linkWe investigate the design of dynamic programming algorithms in unreliable
memories, i.e., in the presence of errors that lead the logical state of some bits to
be read differently from how they were last written. Assuming that a limited number
of memory faults can be inserted at run-time by an adversary with unbounded computational
power, we obtain the first resilient algorithms for a broad range of dynamic
programming problems, devising a general framework that can be applied to both iterative
and recursive implementations. Besides all local dependency problems, where
updates to table entries are determined by the contents of neighboring cells, we also
settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication.
All our algorithms are correct with high probability and match the running
time of their standard non-resilient counterparts while tolerating a polynomial number
of faults. The recursive algorithms are also cache-efficient and can tolerate faults atany level of the memory hierarchy. Our results exploit a careful combination of data
replication, majority techniques, fingerprint computations, and lazy fault detection.
To cope with the complex data access patterns induced by some of our algorithms,
we also devise amplified fingerprints, which might be of independent interest in the
design of resilient algorithms for different problems
A general approach to L(h,k)-label interconnection networks
No full textGiven two non negative integers h and k, an L(h; k)-labeling of a graph G = (V; E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h and nodes at distance 2 take colors at distance at least k. The aim of the L(h; k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be e±ciently solved. In this work the L(h; k)-labeling problem for a new class of graphs, called (l£n)-multistage graphs, is studied. These graphs are characterized to have nodes orga-nized as a matrix and they include the most common interconnection topologies, such as Butter°y-like, Bene·s, CCC, Trivalent Cayley networks. The general al-gorithm presented in this paper leads to an e±cient L(2; 1)-labeling scheme for Butter°y and CCC networks
- …
