Pubblicazioni Aperte DIgitali Sapienza > Informatica > INFORMATICA >

Please use this identifier to cite or link to this item:

Title: On Coding Labeled Trees
Tutor: Petreschi, Rossella
Keywords: Tree encoding
Prufer codes
Optimal Algorithms
Parallel Algorithms
Genetic Algorithms
Informative Labeling Scheme
Issue Date: 2007
Abstract: Trees 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.
Research interests: Algoritmi per memorie soggette a fault Strutture Dati Concorrenti Schemi di etichettatura informativa Algoritmi Paralleli e Distribuiti Codifica di alberi etichettati Colorazione di Grafi
Skills short description: Esperienza di programmazione nei linguaggi: Java, C, C++, ObjectiveC, Perl, SQL, ActionScript, Pascal, ML, SmallTalk, Ada. Esperienza di sviluppo di siti web con tecnologie: Adobe Flash, JavaScript, (X)HTML, CSS, CGI, PHP, ASP, XML. Esperienza nella progettazione di Basi di Dati. Competenze nell’ambito della progettazione e della valutazione dell’usabilità di interfacce utente. Perfetta padronanza delle espressioni regolari. Abilità d’uso di vari programmi di grafica quali: Adobe Firework, Adobe Freehand, Adobe Photoshop, Adobe Illustrator, Jasc Paint Shop Pro. Abilità d’uso di vari software per la programmazione (XCode, Eclipse), l’editing di testi (quali LaTeX, BibTeX e Microsoft Word), l’OCR e la gestione di dati (quali Microsoft Excel e Microsoft Access).
Personal skills keywords: Java, C, C++, ObjectiveC, Perl, SQL, ActionScript, Pascal, ML, SmallTalk, Ada, XCode, Eclipse
Flash, JavaScript, (X)HTML, CSS, CGI, PHP, ASP, XML
MySQL, Microsoft Access
Adobe Firework, Adobe Freehand, Adobe Photoshop, Adobe Illustrator, Jasc Paint Shop Pro.
LaTeX, BibTeX e Microsoft Word, Microsoft Excel

Files in This Item:

File Description SizeFormat
c0_thesis.pdfPhD thesis1.47 MBAdobe PDF

This item is protected by original copyright

Recommend this item

Items in PADIS are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback Sviluppo e manutenzione a cura del CINECA